1 3b0f3d61 2020-01-22 neels /* Myers diff algorithm implementation, invented by Eugene W. Myers [1].
2 3b0f3d61 2020-01-22 neels * Implementations of both the Myers Divide Et Impera (using linear space)
3 3b0f3d61 2020-01-22 neels * and the canonical Myers algorithm (using quadratic space). */
5 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
7 3b0f3d61 2020-01-22 neels * Permission to use, copy, modify, and distribute this software for any
8 3b0f3d61 2020-01-22 neels * purpose with or without fee is hereby granted, provided that the above
9 3b0f3d61 2020-01-22 neels * copyright notice and this permission notice appear in all copies.
11 3b0f3d61 2020-01-22 neels * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 3b0f3d61 2020-01-22 neels * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 3b0f3d61 2020-01-22 neels * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 3b0f3d61 2020-01-22 neels * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 3b0f3d61 2020-01-22 neels * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 3b0f3d61 2020-01-22 neels * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 3b0f3d61 2020-01-22 neels * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 e10a628a 2020-09-16 stsp #include <stdbool.h>
21 fe6d58fb 2020-11-14 naddy #include <stdint.h>
22 e10a628a 2020-09-16 stsp #include <stdlib.h>
23 e10a628a 2020-09-16 stsp #include <string.h>
24 7a54ad3a 2020-09-20 stsp #include <stdio.h>
25 e10a628a 2020-09-16 stsp #include <errno.h>
27 1dfba055 2020-10-07 stsp #include <arraylist.h>
28 1dfba055 2020-10-07 stsp #include <diff_main.h>
30 85ab4559 2020-09-22 stsp #include "diff_internal.h"
31 2a1b94d0 2020-09-26 stsp #include "diff_debug.h"
33 3b0f3d61 2020-01-22 neels /* Myers' diff algorithm [1] is nicely explained in [2].
34 3b0f3d61 2020-01-22 neels * [1] http://www.xmailserver.org/diff2.pdf
35 3b0f3d61 2020-01-22 neels * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
37 3b0f3d61 2020-01-22 neels * Myers approaches finding the smallest diff as a graph problem.
38 3b0f3d61 2020-01-22 neels * The crux is that the original algorithm requires quadratic amount of memory:
39 0d27172a 2020-05-06 neels * both sides' lengths added, and that squared. So if we're diffing lines of
40 0d27172a 2020-05-06 neels * text, two files with 1000 lines each would blow up to a matrix of about
41 0d27172a 2020-05-06 neels * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
42 0d27172a 2020-05-06 neels * The solution is using Myers' "divide and conquer" extension algorithm, which
43 0d27172a 2020-05-06 neels * does the original traversal from both ends of the files to reach a middle
44 0d27172a 2020-05-06 neels * where these "snakes" touch, hence does not need to backtrace the traversal,
45 0d27172a 2020-05-06 neels * and so gets away with only keeping a single column of that huge state matrix
46 0d27172a 2020-05-06 neels * in memory.
49 3b0f3d61 2020-01-22 neels struct diff_box {
50 3b0f3d61 2020-01-22 neels unsigned int left_start;
51 3b0f3d61 2020-01-22 neels unsigned int left_end;
52 3b0f3d61 2020-01-22 neels unsigned int right_start;
53 3b0f3d61 2020-01-22 neels unsigned int right_end;
56 3b0f3d61 2020-01-22 neels /* If the two contents of a file are A B C D E and X B C Y,
57 3b0f3d61 2020-01-22 neels * the Myers diff graph looks like:
61 3b0f3d61 2020-01-22 neels * k-1 0 1 2 3 4 5
62 3b0f3d61 2020-01-22 neels * \ A B C D E
63 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o-o
64 3b0f3d61 2020-01-22 neels * X | | | | | |
65 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o-o
66 3b0f3d61 2020-01-22 neels * B | |\| | | |
67 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o-o
68 3b0f3d61 2020-01-22 neels * C | | |\| | |
69 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-o-o
70 3b0f3d61 2020-01-22 neels * Y | | | | | |\
71 3b0f3d61 2020-01-22 neels * 4 o-o-o-o-o-o c1
75 3b0f3d61 2020-01-22 neels * Moving right means delete an atom from the left-hand-side,
76 3b0f3d61 2020-01-22 neels * Moving down means add an atom from the right-hand-side.
77 0d27172a 2020-05-06 neels * Diagonals indicate identical atoms on both sides, the challenge is to use as
78 0d27172a 2020-05-06 neels * many diagonals as possible.
80 0d27172a 2020-05-06 neels * The original Myers algorithm walks all the way from the top left to the
81 0d27172a 2020-05-06 neels * bottom right, remembers all steps, and then backtraces to find the shortest
82 0d27172a 2020-05-06 neels * path. However, that requires keeping the entire graph in memory, which needs
83 3b0f3d61 2020-01-22 neels * quadratic space.
85 0d27172a 2020-05-06 neels * Myers adds a variant that uses linear space -- note, not linear time, only
86 0d27172a 2020-05-06 neels * linear space: walk forward and backward, find a meeting point in the middle,
87 0d27172a 2020-05-06 neels * and recurse on the two separate sections. This is called "divide and
88 0d27172a 2020-05-06 neels * conquer".
90 0d27172a 2020-05-06 neels * d: the step number, starting with 0, a.k.a. the distance from the starting
92 0d27172a 2020-05-06 neels * k: relative index in the state array for the forward scan, indicating on
93 0d27172a 2020-05-06 neels * which diagonal through the diff graph we currently are.
94 0d27172a 2020-05-06 neels * c: relative index in the state array for the backward scan, indicating the
95 0d27172a 2020-05-06 neels * diagonal number from the bottom up.
97 3b0f3d61 2020-01-22 neels * The "divide and conquer" traversal through the Myers graph looks like this:
99 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 2 1 0
100 3b0f3d61 2020-01-22 neels * ----+--------------------------------------------
104 3b0f3d61 2020-01-22 neels * 3 | 3,0 5,2 2
106 3b0f3d61 2020-01-22 neels * 2 | 2,0 5,3 1
108 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
109 3b0f3d61 2020-01-22 neels * | / / \ /
110 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 -1
112 3b0f3d61 2020-01-22 neels * -1 | 0,1 1,2 3,4 -2
114 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
117 3b0f3d61 2020-01-22 neels * | forward-> <-backward
119 3b0f3d61 2020-01-22 neels * x,y pairs here are the coordinates in the Myers graph:
120 3b0f3d61 2020-01-22 neels * x = atom index in left-side source, y = atom index in the right-side source.
122 0d27172a 2020-05-06 neels * Only one forward column and one backward column are kept in mem, each need at
123 0d27172a 2020-05-06 neels * most left.len + 1 + right.len items. Note that each d step occupies either
124 0d27172a 2020-05-06 neels * the even or the odd items of a column: if e.g. the previous column is in the
125 0d27172a 2020-05-06 neels * odd items, the next column is formed in the even items, without overwriting
126 0d27172a 2020-05-06 neels * the previous column's results.
128 0d27172a 2020-05-06 neels * Also note that from the diagonal index k and the x coordinate, the y
129 0d27172a 2020-05-06 neels * coordinate can be derived:
130 3b0f3d61 2020-01-22 neels * y = x - k
131 0d27172a 2020-05-06 neels * Hence the state array only needs to keep the x coordinate, i.e. the position
132 0d27172a 2020-05-06 neels * in the left-hand file, and the y coordinate, i.e. position in the right-hand
133 0d27172a 2020-05-06 neels * file, is derived from the index in the state array.
135 0d27172a 2020-05-06 neels * The two traces meet at 4,3, the first step (here found in the forward
136 0d27172a 2020-05-06 neels * traversal) where a forward position is on or past a backward traced position
137 0d27172a 2020-05-06 neels * on the same diagonal.
139 3b0f3d61 2020-01-22 neels * This divides the problem space into:
141 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
142 3b0f3d61 2020-01-22 neels * A B C D E
143 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o
144 3b0f3d61 2020-01-22 neels * X | | | | |
145 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o
146 3b0f3d61 2020-01-22 neels * B | |\| | |
147 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o
148 3b0f3d61 2020-01-22 neels * C | | |\| |
149 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-*-o *: forward and backward meet here
153 3b0f3d61 2020-01-22 neels * Doing the same on each section lead to:
155 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
156 3b0f3d61 2020-01-22 neels * A B C D E
159 3b0f3d61 2020-01-22 neels * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
160 3b0f3d61 2020-01-22 neels * B \ f: then forward d=2 reaches here (sliding down the snake)
161 3b0f3d61 2020-01-22 neels * 2 o As result, the box from b to f is found to be identical;
162 0d27172a 2020-05-06 neels * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial
163 0d27172a 2020-05-06 neels * 3 f-o tail 3,3 to 4,3.
167 3b0f3d61 2020-01-22 neels * 4 o *: forward and backward meet here
169 3b0f3d61 2020-01-22 neels * and solving the last top left box gives:
171 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
172 3b0f3d61 2020-01-22 neels * A B C D E -A
173 3b0f3d61 2020-01-22 neels * 0 o-o +X
185 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))
186 3b0f3d61 2020-01-22 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
187 3b0f3d61 2020-01-22 neels #define k_to_c(K, DELTA) ((K) + (DELTA))
188 3b0f3d61 2020-01-22 neels #define c_to_k(C, DELTA) ((C) - (DELTA))
190 3b0f3d61 2020-01-22 neels /* Do one forwards step in the "divide and conquer" graph traversal.
191 3b0f3d61 2020-01-22 neels * left: the left side to diff.
192 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
193 0d27172a 2020-05-06 neels * kd_forward: the traversal state for forwards traversal, modified by this
194 0d27172a 2020-05-06 neels * function.
195 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
196 0d27172a 2020-05-06 neels * kd_forward points at the center of the state array, allowing
197 0d27172a 2020-05-06 neels * negative indexes.
198 0d27172a 2020-05-06 neels * kd_backward: the traversal state for backwards traversal, to find a meeting
200 0d27172a 2020-05-06 neels * Since forwards is done first, kd_backward will be valid for d -
201 0d27172a 2020-05-06 neels * 1, not d.
202 0d27172a 2020-05-06 neels * kd_backward points at the center of the state array, allowing
203 0d27172a 2020-05-06 neels * negative indexes.
204 0d27172a 2020-05-06 neels * d: Step or distance counter, indicating for what value of d the kd_forward
205 0d27172a 2020-05-06 neels * should be populated.
206 0d27172a 2020-05-06 neels * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
207 0d27172a 2020-05-06 neels * be for d == 0.
208 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
209 0d27172a 2020-05-06 neels * Return true when a meeting point has been identified.
211 ac2eeeff 2020-09-20 neels static int
212 ac2eeeff 2020-09-20 neels diff_divide_myers_forward(bool *found_midpoint,
213 ac2eeeff 2020-09-20 neels struct diff_data *left, struct diff_data *right,
214 61a7b578 2020-05-06 neels int *kd_forward, int *kd_backward, int d,
215 61a7b578 2020-05-06 neels struct diff_box *meeting_snake)
217 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
220 984ca65b 2020-10-11 neels int prev_x;
221 984ca65b 2020-10-11 neels int prev_y;
222 984ca65b 2020-10-11 neels int x_before_slide;
223 ac2eeeff 2020-09-20 neels *found_midpoint = false;
225 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
226 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
227 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the Myers
228 0d27172a 2020-05-06 neels * graph, don't calculate it. */
229 3b0f3d61 2020-01-22 neels if (k < 0) {
230 0d27172a 2020-05-06 neels /* We are traversing negatively, and already
231 0d27172a 2020-05-06 neels * below the entire graph, nothing will come of
232 0d27172a 2020-05-06 neels * this. */
233 f579bf77 2020-10-20 neels debug(" break\n");
236 f579bf77 2020-10-20 neels debug(" continue\n");
239 3b0f3d61 2020-01-22 neels if (d == 0) {
240 0d27172a 2020-05-06 neels /* This is the initializing step. There is no prev_k
241 0d27172a 2020-05-06 neels * yet, get the initial x from the top left of the Myers
242 0d27172a 2020-05-06 neels * graph. */
244 70fb5a47 2020-10-15 neels prev_x = x;
245 70fb5a47 2020-10-15 neels prev_y = xk_to_y(x, k);
247 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring moving rightwards in
248 0d27172a 2020-05-06 neels * the Myers graph.
249 0d27172a 2020-05-06 neels * For this, all k should derive from k - 1, only the bottom
250 0d27172a 2020-05-06 neels * most k derive from k + 1:
252 3b0f3d61 2020-01-22 neels * | d= 0 1 2
253 3b0f3d61 2020-01-22 neels * ----+----------------
255 3b0f3d61 2020-01-22 neels * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
259 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
261 0d27172a 2020-05-06 neels * -1 | 0,1 <-- bottom most for d=1 from
262 0d27172a 2020-05-06 neels * | \\ prev_k = -1 + 1 = 0
263 0d27172a 2020-05-06 neels * -2 | 0,2 <-- bottom most for d=2 from
264 0d27172a 2020-05-06 neels * prev_k = -2 + 1 = -1
266 0d27172a 2020-05-06 neels * Except when a k + 1 from a previous run already means a
267 0d27172a 2020-05-06 neels * further advancement in the graph.
268 3b0f3d61 2020-01-22 neels * If k == d, there is no k + 1 and k - 1 is the only option.
269 0d27172a 2020-05-06 neels * If k < d, use k + 1 in case that yields a larger x. Also use
270 0d27172a 2020-05-06 neels * k + 1 if k - 1 is outside the graph.
272 0d27172a 2020-05-06 neels else if (k > -d
273 0d27172a 2020-05-06 neels && (k == d
274 0d27172a 2020-05-06 neels || (k - 1 >= -(int)right->atoms.len
275 0d27172a 2020-05-06 neels && kd_forward[k - 1] >= kd_forward[k + 1]))) {
276 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
277 0d27172a 2020-05-06 neels * From position prev_k, step to the right in the Myers
278 0d27172a 2020-05-06 neels * graph: x += 1.
280 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
281 984ca65b 2020-10-11 neels prev_x = kd_forward[prev_k];
282 984ca65b 2020-10-11 neels prev_y = xk_to_y(prev_x, prev_k);
283 3b0f3d61 2020-01-22 neels x = prev_x + 1;
285 3b0f3d61 2020-01-22 neels /* The bottom most one.
286 0d27172a 2020-05-06 neels * From position prev_k, step to the bottom in the Myers
287 0d27172a 2020-05-06 neels * graph: y += 1.
288 0d27172a 2020-05-06 neels * Incrementing y is achieved by decrementing k while
289 0d27172a 2020-05-06 neels * keeping the same x.
290 3b0f3d61 2020-01-22 neels * (since we're deriving y from y = x - k).
292 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
293 984ca65b 2020-10-11 neels prev_x = kd_forward[prev_k];
294 984ca65b 2020-10-11 neels prev_y = xk_to_y(prev_x, prev_k);
295 3b0f3d61 2020-01-22 neels x = prev_x;
298 984ca65b 2020-10-11 neels x_before_slide = x;
299 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
300 b3fb4686 2020-09-20 neels while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) {
301 b3fb4686 2020-09-20 neels bool same;
302 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
303 b3fb4686 2020-09-20 neels &left->atoms.head[x],
304 b3fb4686 2020-09-20 neels &right->atoms.head[
305 b3fb4686 2020-09-20 neels xk_to_y(x, k)]);
308 b3fb4686 2020-09-20 neels if (!same)
312 3b0f3d61 2020-01-22 neels kd_forward[k] = x;
314 c5419a05 2020-05-05 neels if (x_before_slide != x) {
315 c5419a05 2020-05-05 neels debug(" down %d similar lines\n", x - x_before_slide);
321 3b0f3d61 2020-01-22 neels for (fi = d; fi >= k; fi--) {
322 0d27172a 2020-05-06 neels debug("kd_forward[%d] = (%d, %d)\n", fi,
323 0d27172a 2020-05-06 neels kd_forward[fi], kd_forward[fi] - fi);
329 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
330 3b0f3d61 2020-01-22 neels || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
333 0d27172a 2020-05-06 neels /* Figured out a new forwards traversal, see if this has gone
334 0d27172a 2020-05-06 neels * onto or even past a preceding backwards traversal.
336 0d27172a 2020-05-06 neels * If the delta in length is odd, then d and backwards_d hit the
337 0d27172a 2020-05-06 neels * same state indexes:
338 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
339 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
345 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,3 1
347 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,4<-- 0
349 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,4 -1
351 3b0f3d61 2020-01-22 neels * -1 | 0,1 -2
353 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
356 0d27172a 2020-05-06 neels * If the delta is even, they end up off-by-one, i.e. on
357 0d27172a 2020-05-06 neels * different diagonals:
359 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
360 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
364 3b0f3d61 2020-01-22 neels * 2 | 2,0 off 2
366 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 1
367 3b0f3d61 2020-01-22 neels * | / // \
368 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4<-- 0
370 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4 -1
372 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
375 0d27172a 2020-05-06 neels * So in the forward path, we can only match up diagonals when
376 0d27172a 2020-05-06 neels * the delta is odd.
378 fd42ca98 2020-05-05 neels if ((delta & 1) == 0)
380 0d27172a 2020-05-06 neels /* Forwards is done first, so the backwards one was still at
381 0d27172a 2020-05-06 neels * d - 1. Can't do this for d == 0. */
382 3b0f3d61 2020-01-22 neels int backwards_d = d - 1;
383 fd42ca98 2020-05-05 neels if (backwards_d < 0)
386 0d27172a 2020-05-06 neels /* If both sides have the same length, forward and backward
387 0d27172a 2020-05-06 neels * start on the same diagonal, meaning the backwards state index
389 0d27172a 2020-05-06 neels * As soon as the lengths are not the same, the backwards
390 0d27172a 2020-05-06 neels * traversal starts on a different diagonal, and c = k shifted
391 0d27172a 2020-05-06 neels * by the difference in length.
393 fd42ca98 2020-05-05 neels int c = k_to_c(k, delta);
395 0d27172a 2020-05-06 neels /* When the file sizes are very different, the traversal trees
396 0d27172a 2020-05-06 neels * start on far distant diagonals.
397 0d27172a 2020-05-06 neels * They don't necessarily meet straight on. See whether this
398 0d27172a 2020-05-06 neels * forward value is on a diagonal that is also valid in
399 0d27172a 2020-05-06 neels * kd_backward[], and match them if so. */
400 fd42ca98 2020-05-05 neels if (c >= -backwards_d && c <= backwards_d) {
401 0d27172a 2020-05-06 neels /* Current k is on a diagonal that exists in
402 0d27172a 2020-05-06 neels * kd_backward[]. If the two x positions have met or
403 0d27172a 2020-05-06 neels * passed (forward walked onto or past backward), then
404 0d27172a 2020-05-06 neels * we've found a midpoint / a mid-box.
406 0d27172a 2020-05-06 neels * When forwards and backwards traversals meet, the
407 0d27172a 2020-05-06 neels * endpoints of the mid-snake are not the two points in
408 0d27172a 2020-05-06 neels * kd_forward and kd_backward, but rather the section
409 0d27172a 2020-05-06 neels * that was slid (if any) of the current
410 0d27172a 2020-05-06 neels * forward/backward traversal only.
412 f71e8098 2020-05-05 neels * For example:
434 0d27172a 2020-05-06 neels * The forward traversal reached M from the top and slid
435 0d27172a 2020-05-06 neels * downwards to A. The backward traversal already
436 0d27172a 2020-05-06 neels * reached X, which is not a straight line from M
437 0d27172a 2020-05-06 neels * anymore, so picking a mid-snake from M to X would
438 0d27172a 2020-05-06 neels * yield a mistake.
440 0d27172a 2020-05-06 neels * The correct mid-snake is between M and A. M is where
441 0d27172a 2020-05-06 neels * the forward traversal hit the diagonal that the
442 0d27172a 2020-05-06 neels * backward traversal has already passed, and A is what
443 0d27172a 2020-05-06 neels * it reaches when sliding down identical lines.
445 fd42ca98 2020-05-05 neels int backward_x = kd_backward[c];
446 f71e8098 2020-05-05 neels if (x >= backward_x) {
447 984ca65b 2020-10-11 neels if (x_before_slide != x) {
448 984ca65b 2020-10-11 neels /* met after sliding up a mid-snake */
449 984ca65b 2020-10-11 neels *meeting_snake = (struct diff_box){
450 984ca65b 2020-10-11 neels .left_start = x_before_slide,
451 984ca65b 2020-10-11 neels .left_end = x,
452 984ca65b 2020-10-11 neels .right_start = xc_to_y(x_before_slide,
453 984ca65b 2020-10-11 neels c, delta),
454 984ca65b 2020-10-11 neels .right_end = xk_to_y(x, k),
457 984ca65b 2020-10-11 neels /* met after a side step, non-identical
458 984ca65b 2020-10-11 neels * line. Mark that as box divider
459 984ca65b 2020-10-11 neels * instead. This makes sure that
460 984ca65b 2020-10-11 neels * myers_divide never returns the same
461 984ca65b 2020-10-11 neels * box that came as input, avoiding
462 984ca65b 2020-10-11 neels * "infinite" looping. */
463 984ca65b 2020-10-11 neels *meeting_snake = (struct diff_box){
464 984ca65b 2020-10-11 neels .left_start = prev_x,
465 984ca65b 2020-10-11 neels .left_end = x,
466 984ca65b 2020-10-11 neels .right_start = prev_y,
467 984ca65b 2020-10-11 neels .right_end = xk_to_y(x, k),
470 fd42ca98 2020-05-05 neels debug("HIT x=(%u,%u) - y=(%u,%u)\n",
471 fd42ca98 2020-05-05 neels meeting_snake->left_start,
472 fd42ca98 2020-05-05 neels meeting_snake->right_start,
473 fd42ca98 2020-05-05 neels meeting_snake->left_end,
474 fd42ca98 2020-05-05 neels meeting_snake->right_end);
475 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL,
476 0d27172a 2020-05-06 neels kd_forward, d,
477 0d27172a 2020-05-06 neels kd_backward, d-1);
478 ac2eeeff 2020-09-20 neels *found_midpoint = true;
487 3b0f3d61 2020-01-22 neels /* Do one backwards step in the "divide and conquer" graph traversal.
488 3b0f3d61 2020-01-22 neels * left: the left side to diff.
489 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
490 0d27172a 2020-05-06 neels * kd_forward: the traversal state for forwards traversal, to find a meeting
492 0d27172a 2020-05-06 neels * Since forwards is done first, after this, both kd_forward and
493 0d27172a 2020-05-06 neels * kd_backward will be valid for d.
494 0d27172a 2020-05-06 neels * kd_forward points at the center of the state array, allowing
495 0d27172a 2020-05-06 neels * negative indexes.
496 0d27172a 2020-05-06 neels * kd_backward: the traversal state for backwards traversal, to find a meeting
498 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
499 0d27172a 2020-05-06 neels * kd_backward points at the center of the state array, allowing
500 0d27172a 2020-05-06 neels * negative indexes.
501 0d27172a 2020-05-06 neels * d: Step or distance counter, indicating for what value of d the kd_backward
502 0d27172a 2020-05-06 neels * should be populated.
503 0d27172a 2020-05-06 neels * Before the first invocation, kd_backward[0] shall point at the bottom
504 0d27172a 2020-05-06 neels * right of the Myers graph (left.len, right.len).
505 3b0f3d61 2020-01-22 neels * The first invocation will be for d == 1.
506 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
507 0d27172a 2020-05-06 neels * Return true when a meeting point has been identified.
509 ac2eeeff 2020-09-20 neels static int
510 ac2eeeff 2020-09-20 neels diff_divide_myers_backward(bool *found_midpoint,
511 ac2eeeff 2020-09-20 neels struct diff_data *left, struct diff_data *right,
512 61a7b578 2020-05-06 neels int *kd_forward, int *kd_backward, int d,
513 61a7b578 2020-05-06 neels struct diff_box *meeting_snake)
515 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
518 984ca65b 2020-10-11 neels int prev_x;
519 984ca65b 2020-10-11 neels int prev_y;
520 984ca65b 2020-10-11 neels int x_before_slide;
522 ac2eeeff 2020-09-20 neels *found_midpoint = false;
524 3b0f3d61 2020-01-22 neels for (c = d; c >= -d; c -= 2) {
525 3b0f3d61 2020-01-22 neels if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
526 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the Myers
527 0d27172a 2020-05-06 neels * graph, don't calculate it. */
528 3b0f3d61 2020-01-22 neels if (c < 0) {
529 0d27172a 2020-05-06 neels /* We are traversing negatively, and already
530 0d27172a 2020-05-06 neels * below the entire graph, nothing will come of
531 0d27172a 2020-05-06 neels * this. */
536 3b0f3d61 2020-01-22 neels if (d == 0) {
537 0d27172a 2020-05-06 neels /* This is the initializing step. There is no prev_c
538 0d27172a 2020-05-06 neels * yet, get the initial x from the bottom right of the
539 0d27172a 2020-05-06 neels * Myers graph. */
540 3b0f3d61 2020-01-22 neels x = left->atoms.len;
541 70fb5a47 2020-10-15 neels prev_x = x;
542 70fb5a47 2020-10-15 neels prev_y = xc_to_y(x, c, delta);
544 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring moving rightwards in
545 0d27172a 2020-05-06 neels * the Myers graph.
546 0d27172a 2020-05-06 neels * For this, all c should derive from c - 1, only the bottom
547 0d27172a 2020-05-06 neels * most c derive from c + 1:
550 3b0f3d61 2020-01-22 neels * ---------------------------------------------------
554 3b0f3d61 2020-01-22 neels * from prev_c = c - 1 --> 5,2 2
558 3b0f3d61 2020-01-22 neels * 4,3 5,4<-- 0
560 3b0f3d61 2020-01-22 neels * bottom most for d=1 from c + 1 --> 4,4 -1
562 3b0f3d61 2020-01-22 neels * bottom most for d=2 --> 3,4 -2
564 0d27172a 2020-05-06 neels * Except when a c + 1 from a previous run already means a
565 0d27172a 2020-05-06 neels * further advancement in the graph.
566 3b0f3d61 2020-01-22 neels * If c == d, there is no c + 1 and c - 1 is the only option.
567 0d27172a 2020-05-06 neels * If c < d, use c + 1 in case that yields a larger x.
568 0d27172a 2020-05-06 neels * Also use c + 1 if c - 1 is outside the graph.
570 3b0f3d61 2020-01-22 neels else if (c > -d && (c == d
571 3b0f3d61 2020-01-22 neels || (c - 1 >= -(int)right->atoms.len
572 3b0f3d61 2020-01-22 neels && kd_backward[c - 1] <= kd_backward[c + 1]))) {
573 3b0f3d61 2020-01-22 neels /* A top one.
574 0d27172a 2020-05-06 neels * From position prev_c, step upwards in the Myers
575 0d27172a 2020-05-06 neels * graph: y -= 1.
576 0d27172a 2020-05-06 neels * Decrementing y is achieved by incrementing c while
577 0d27172a 2020-05-06 neels * keeping the same x. (since we're deriving y from
578 0d27172a 2020-05-06 neels * y = x - c + delta).
580 3b0f3d61 2020-01-22 neels int prev_c = c - 1;
581 984ca65b 2020-10-11 neels prev_x = kd_backward[prev_c];
582 984ca65b 2020-10-11 neels prev_y = xc_to_y(prev_x, prev_c, delta);
583 3b0f3d61 2020-01-22 neels x = prev_x;
585 3b0f3d61 2020-01-22 neels /* The bottom most one.
586 0d27172a 2020-05-06 neels * From position prev_c, step to the left in the Myers
587 0d27172a 2020-05-06 neels * graph: x -= 1.
589 3b0f3d61 2020-01-22 neels int prev_c = c + 1;
590 984ca65b 2020-10-11 neels prev_x = kd_backward[prev_c];
591 984ca65b 2020-10-11 neels prev_y = xc_to_y(prev_x, prev_c, delta);
592 3b0f3d61 2020-01-22 neels x = prev_x - 1;
595 0d27172a 2020-05-06 neels /* Slide up any snake that we might find here (sections of
596 0d27172a 2020-05-06 neels * identical lines on both sides). */
598 0d27172a 2020-05-06 neels debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c,
600 0d27172a 2020-05-06 neels xc_to_y(x, c, delta)-1);
601 3b0f3d61 2020-01-22 neels if (x > 0) {
602 0d27172a 2020-05-06 neels debug(" l=");
603 0d27172a 2020-05-06 neels debug_dump_atom(left, right, &left->atoms.head[x-1]);
605 3b0f3d61 2020-01-22 neels if (xc_to_y(x, c, delta) > 0) {
606 0d27172a 2020-05-06 neels debug(" r=");
607 0d27172a 2020-05-06 neels debug_dump_atom(right, left,
608 0d27172a 2020-05-06 neels &right->atoms.head[xc_to_y(x, c, delta)-1]);
611 984ca65b 2020-10-11 neels x_before_slide = x;
612 b3fb4686 2020-09-20 neels while (x > 0 && xc_to_y(x, c, delta) > 0) {
613 b3fb4686 2020-09-20 neels bool same;
614 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
615 b3fb4686 2020-09-20 neels &left->atoms.head[x-1],
616 b3fb4686 2020-09-20 neels &right->atoms.head[
617 b3fb4686 2020-09-20 neels xc_to_y(x, c, delta)-1]);
620 b3fb4686 2020-09-20 neels if (!same)
624 3b0f3d61 2020-01-22 neels kd_backward[c] = x;
626 c5419a05 2020-05-05 neels if (x_before_slide != x) {
627 c5419a05 2020-05-05 neels debug(" up %d similar lines\n", x_before_slide - x);
630 3b0f3d61 2020-01-22 neels if (DEBUG) {
632 3b0f3d61 2020-01-22 neels for (fi = d; fi >= c; fi--) {
633 0d27172a 2020-05-06 neels debug("kd_backward[%d] = (%d, %d)\n",
635 0d27172a 2020-05-06 neels kd_backward[fi],
636 3b0f3d61 2020-01-22 neels kd_backward[fi] - fi + delta);
641 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
642 0d27172a 2020-05-06 neels || xc_to_y(x, c, delta) < 0
643 0d27172a 2020-05-06 neels || xc_to_y(x, c, delta) > right->atoms.len)
646 0d27172a 2020-05-06 neels /* Figured out a new backwards traversal, see if this has gone
647 0d27172a 2020-05-06 neels * onto or even past a preceding forwards traversal.
649 0d27172a 2020-05-06 neels * If the delta in length is even, then d and backwards_d hit
650 0d27172a 2020-05-06 neels * the same state indexes -- note how this is different from in
651 0d27172a 2020-05-06 neels * the forwards traversal, because now both d are the same:
653 3b0f3d61 2020-01-22 neels * | d= 0 1 2 2 1 0
654 3b0f3d61 2020-01-22 neels * ----+---------------- --------------------
660 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,2 2
662 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,3 1
664 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,3 5,4<-- 0
666 3b0f3d61 2020-01-22 neels * -1 | 0,1 4,4 -1
668 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
671 0d27172a 2020-05-06 neels * If the delta is odd, they end up off-by-one, i.e. on
672 0d27172a 2020-05-06 neels * different diagonals.
673 0d27172a 2020-05-06 neels * So in the backward path, we can only match up diagonals when
674 0d27172a 2020-05-06 neels * the delta is even.
676 0d27172a 2020-05-06 neels if ((delta & 1) != 0)
678 0d27172a 2020-05-06 neels /* Forwards was done first, now both d are the same. */
679 0d27172a 2020-05-06 neels int forwards_d = d;
681 0d27172a 2020-05-06 neels /* As soon as the lengths are not the same, the
682 0d27172a 2020-05-06 neels * backwards traversal starts on a different diagonal,
683 0d27172a 2020-05-06 neels * and c = k shifted by the difference in length.
685 0d27172a 2020-05-06 neels int k = c_to_k(c, delta);
687 0d27172a 2020-05-06 neels /* When the file sizes are very different, the traversal trees
688 0d27172a 2020-05-06 neels * start on far distant diagonals.
689 0d27172a 2020-05-06 neels * They don't necessarily meet straight on. See whether this
690 0d27172a 2020-05-06 neels * backward value is also on a valid diagonal in kd_forward[],
691 0d27172a 2020-05-06 neels * and match them if so. */
692 0d27172a 2020-05-06 neels if (k >= -forwards_d && k <= forwards_d) {
693 0d27172a 2020-05-06 neels /* Current c is on a diagonal that exists in
694 0d27172a 2020-05-06 neels * kd_forward[]. If the two x positions have met or
695 0d27172a 2020-05-06 neels * passed (backward walked onto or past forward), then
696 0d27172a 2020-05-06 neels * we've found a midpoint / a mid-box.
698 0d27172a 2020-05-06 neels * When forwards and backwards traversals meet, the
699 0d27172a 2020-05-06 neels * endpoints of the mid-snake are not the two points in
700 0d27172a 2020-05-06 neels * kd_forward and kd_backward, but rather the section
701 0d27172a 2020-05-06 neels * that was slid (if any) of the current
702 0d27172a 2020-05-06 neels * forward/backward traversal only.
704 0d27172a 2020-05-06 neels * For example:
724 0d27172a 2020-05-06 neels * The backward traversal reached M from the bottom and
725 0d27172a 2020-05-06 neels * slid upwards. The forward traversal already reached
726 0d27172a 2020-05-06 neels * X, which is not a straight line from M anymore, so
727 0d27172a 2020-05-06 neels * picking a mid-snake from M to X would yield a
728 0d27172a 2020-05-06 neels * mistake.
730 0d27172a 2020-05-06 neels * The correct mid-snake is between M and A. M is where
731 0d27172a 2020-05-06 neels * the backward traversal hit the diagonal that the
732 0d27172a 2020-05-06 neels * forwards traversal has already passed, and A is what
733 0d27172a 2020-05-06 neels * it reaches when sliding up identical lines.
736 0d27172a 2020-05-06 neels int forward_x = kd_forward[k];
737 0d27172a 2020-05-06 neels if (forward_x >= x) {
738 984ca65b 2020-10-11 neels if (x_before_slide != x) {
739 984ca65b 2020-10-11 neels /* met after sliding down a mid-snake */
740 984ca65b 2020-10-11 neels *meeting_snake = (struct diff_box){
741 984ca65b 2020-10-11 neels .left_start = x,
742 984ca65b 2020-10-11 neels .left_end = x_before_slide,
743 984ca65b 2020-10-11 neels .right_start = xc_to_y(x, c, delta),
744 984ca65b 2020-10-11 neels .right_end = xk_to_y(x_before_slide, k),
747 984ca65b 2020-10-11 neels /* met after a side step, non-identical
748 984ca65b 2020-10-11 neels * line. Mark that as box divider
749 984ca65b 2020-10-11 neels * instead. This makes sure that
750 984ca65b 2020-10-11 neels * myers_divide never returns the same
751 984ca65b 2020-10-11 neels * box that came as input, avoiding
752 984ca65b 2020-10-11 neels * "infinite" looping. */
753 984ca65b 2020-10-11 neels *meeting_snake = (struct diff_box){
754 984ca65b 2020-10-11 neels .left_start = x,
755 984ca65b 2020-10-11 neels .left_end = prev_x,
756 984ca65b 2020-10-11 neels .right_start = xc_to_y(x, c, delta),
757 984ca65b 2020-10-11 neels .right_end = prev_y,
760 0d27172a 2020-05-06 neels debug("HIT x=%u,%u - y=%u,%u\n",
761 0d27172a 2020-05-06 neels meeting_snake->left_start,
762 0d27172a 2020-05-06 neels meeting_snake->right_start,
763 0d27172a 2020-05-06 neels meeting_snake->left_end,
764 0d27172a 2020-05-06 neels meeting_snake->right_end);
765 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL,
766 0d27172a 2020-05-06 neels kd_forward, d,
767 0d27172a 2020-05-06 neels kd_backward, d);
768 ac2eeeff 2020-09-20 neels *found_midpoint = true;
776 cd25827e 2020-09-20 neels /* Integer square root approximation */
777 cd25827e 2020-09-20 neels static int
778 cd25827e 2020-09-20 neels shift_sqrt(int val)
781 cd25827e 2020-09-20 neels for (i = 1; val > 0; val >>= 2)
786 60c6aae1 2020-11-22 stsp #define DIFF_EFFORT_MIN 1024
788 0d27172a 2020-05-06 neels /* Myers "Divide et Impera": tracing forwards from the start and backwards from
789 0d27172a 2020-05-06 neels * the end to find a midpoint that divides the problem into smaller chunks.
790 0d27172a 2020-05-06 neels * Requires only linear amounts of memory. */
792 0d27172a 2020-05-06 neels diff_algo_myers_divide(const struct diff_algo_config *algo_config,
793 0d27172a 2020-05-06 neels struct diff_state *state)
795 3e6cba3a 2020-08-13 stsp int rc = ENOMEM;
796 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
797 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
798 8be88dfa 2020-10-21 stsp int *kd_buf;
800 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
801 3b0f3d61 2020-01-22 neels debug("left:\n");
802 3b0f3d61 2020-01-22 neels debug_dump(left);
803 3b0f3d61 2020-01-22 neels debug("right:\n");
804 3b0f3d61 2020-01-22 neels debug_dump(right);
806 0d27172a 2020-05-06 neels /* Allocate two columns of a Myers graph, one for the forward and one
807 0d27172a 2020-05-06 neels * for the backward traversal. */
808 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
809 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1;
810 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len << 1;
812 8be88dfa 2020-10-21 stsp if (state->kd_buf_size < kd_buf_size) {
813 8be88dfa 2020-10-21 stsp kd_buf = reallocarray(state->kd_buf, kd_buf_size,
814 8be88dfa 2020-10-21 stsp sizeof(int));
815 8be88dfa 2020-10-21 stsp if (!kd_buf)
816 8be88dfa 2020-10-21 stsp return ENOMEM;
817 8be88dfa 2020-10-21 stsp state->kd_buf = kd_buf;
818 8be88dfa 2020-10-21 stsp state->kd_buf_size = kd_buf_size;
820 8be88dfa 2020-10-21 stsp kd_buf = state->kd_buf;
822 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
823 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
824 3b0f3d61 2020-01-22 neels int *kd_forward = kd_buf;
825 3b0f3d61 2020-01-22 neels int *kd_backward = kd_buf + kd_len;
826 cd25827e 2020-09-20 neels int max_effort = shift_sqrt(max/2);
828 60c6aae1 2020-11-22 stsp if (max_effort < DIFF_EFFORT_MIN)
829 60c6aae1 2020-11-22 stsp max_effort = DIFF_EFFORT_MIN;
831 0d27172a 2020-05-06 neels /* The 'k' axis in Myers spans positive and negative indexes, so point
832 0d27172a 2020-05-06 neels * the kd to the middle.
833 3b0f3d61 2020-01-22 neels * It is then possible to index from -max/2 .. max/2. */
834 3b0f3d61 2020-01-22 neels kd_forward += max/2;
835 3b0f3d61 2020-01-22 neels kd_backward += max/2;
838 3b0f3d61 2020-01-22 neels struct diff_box mid_snake = {};
839 a45330b1 2020-05-05 neels bool found_midpoint = false;
840 3b0f3d61 2020-01-22 neels for (d = 0; d <= (max/2); d++) {
842 ac2eeeff 2020-09-20 neels r = diff_divide_myers_forward(&found_midpoint, left, right,
843 ac2eeeff 2020-09-20 neels kd_forward, kd_backward, d,
844 ac2eeeff 2020-09-20 neels &mid_snake);
847 a45330b1 2020-05-05 neels if (found_midpoint)
849 ac2eeeff 2020-09-20 neels r = diff_divide_myers_backward(&found_midpoint, left, right,
850 ac2eeeff 2020-09-20 neels kd_forward, kd_backward, d,
851 ac2eeeff 2020-09-20 neels &mid_snake);
854 a45330b1 2020-05-05 neels if (found_midpoint)
857 cd25827e 2020-09-20 neels /* Limit the effort spent looking for a mid snake. If files have
858 cd25827e 2020-09-20 neels * very few lines in common, the effort spent to find nice mid
859 cd25827e 2020-09-20 neels * snakes is just not worth it, the diff result will still be
860 cd25827e 2020-09-20 neels * essentially minus everything on the left, plus everything on
861 cd25827e 2020-09-20 neels * the right, with a few useless matches here and there. */
862 cd25827e 2020-09-20 neels if (d > max_effort) {
863 cd25827e 2020-09-20 neels /* pick the furthest reaching point from
864 cd25827e 2020-09-20 neels * kd_forward and kd_backward, and use that as a
865 cd25827e 2020-09-20 neels * midpoint, to not step into another diff algo
866 cd25827e 2020-09-20 neels * recursion with unchanged box. */
867 cd25827e 2020-09-20 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
868 70fb5a47 2020-10-15 neels int x = 0;
871 cd25827e 2020-09-20 neels int best_forward_i = 0;
872 cd25827e 2020-09-20 neels int best_forward_distance = 0;
873 cd25827e 2020-09-20 neels int best_backward_i = 0;
874 cd25827e 2020-09-20 neels int best_backward_distance = 0;
875 cd25827e 2020-09-20 neels int distance;
876 cd25827e 2020-09-20 neels int best_forward_x;
877 cd25827e 2020-09-20 neels int best_forward_y;
878 cd25827e 2020-09-20 neels int best_backward_x;
879 cd25827e 2020-09-20 neels int best_backward_y;
881 f579bf77 2020-10-20 neels debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort);
882 f579bf77 2020-10-20 neels debug_dump_myers_graph(left, right, NULL,
883 f579bf77 2020-10-20 neels kd_forward, d,
884 f579bf77 2020-10-20 neels kd_backward, d);
886 cd25827e 2020-09-20 neels for (i = d; i >= -d; i -= 2) {
887 cd25827e 2020-09-20 neels if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) {
888 cd25827e 2020-09-20 neels x = kd_forward[i];
889 cd25827e 2020-09-20 neels y = xk_to_y(x, i);
890 cd25827e 2020-09-20 neels distance = x + y;
891 cd25827e 2020-09-20 neels if (distance > best_forward_distance) {
892 cd25827e 2020-09-20 neels best_forward_distance = distance;
893 cd25827e 2020-09-20 neels best_forward_i = i;
897 cd25827e 2020-09-20 neels if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) {
898 cd25827e 2020-09-20 neels x = kd_backward[i];
899 cd25827e 2020-09-20 neels y = xc_to_y(x, i, delta);
900 cd25827e 2020-09-20 neels distance = (right->atoms.len - x)
901 cd25827e 2020-09-20 neels + (left->atoms.len - y);
902 cd25827e 2020-09-20 neels if (distance >= best_backward_distance) {
903 cd25827e 2020-09-20 neels best_backward_distance = distance;
904 cd25827e 2020-09-20 neels best_backward_i = i;
909 cd25827e 2020-09-20 neels /* The myers-divide didn't meet in the middle. We just
910 cd25827e 2020-09-20 neels * figured out the places where the forward path
911 cd25827e 2020-09-20 neels * advanced the most, and the backward path advanced the
912 cd25827e 2020-09-20 neels * most. Just divide at whichever one of those two is better.
920 cd25827e 2020-09-20 neels * F <-- cut here
924 cd25827e 2020-09-20 neels * or here --> B
932 cd25827e 2020-09-20 neels best_forward_x = kd_forward[best_forward_i];
933 cd25827e 2020-09-20 neels best_forward_y = xk_to_y(best_forward_x, best_forward_i);
934 cd25827e 2020-09-20 neels best_backward_x = kd_backward[best_backward_i];
935 926387ed 2020-10-20 neels best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta);
937 cd25827e 2020-09-20 neels if (best_forward_distance >= best_backward_distance) {
938 cd25827e 2020-09-20 neels x = best_forward_x;
939 cd25827e 2020-09-20 neels y = best_forward_y;
941 cd25827e 2020-09-20 neels x = best_backward_x;
942 cd25827e 2020-09-20 neels y = best_backward_y;
945 cd25827e 2020-09-20 neels debug("max_effort cut at x=%d y=%d\n", x, y);
946 cd25827e 2020-09-20 neels if (x < 0 || y < 0
947 cd25827e 2020-09-20 neels || x > left->atoms.len || y > right->atoms.len)
950 cd25827e 2020-09-20 neels found_midpoint = true;
951 cd25827e 2020-09-20 neels mid_snake = (struct diff_box){
952 cd25827e 2020-09-20 neels .left_start = x,
953 cd25827e 2020-09-20 neels .left_end = x,
954 cd25827e 2020-09-20 neels .right_start = y,
955 cd25827e 2020-09-20 neels .right_end = y,
961 a45330b1 2020-05-05 neels if (!found_midpoint) {
962 0d27172a 2020-05-06 neels /* Divide and conquer failed to find a meeting point. Use the
963 0d27172a 2020-05-06 neels * fallback_algo defined in the algo_config (leave this to the
964 0d27172a 2020-05-06 neels * caller). This is just paranoia/sanity, we normally should
965 0d27172a 2020-05-06 neels * always find a midpoint.
967 3b0f3d61 2020-01-22 neels debug(" no midpoint \n");
968 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
969 3b0f3d61 2020-01-22 neels goto return_rc;
971 3b0f3d61 2020-01-22 neels debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
972 3b0f3d61 2020-01-22 neels mid_snake.left_start, mid_snake.left_end, left->atoms.len,
973 0d27172a 2020-05-06 neels mid_snake.right_start, mid_snake.right_end,
974 0d27172a 2020-05-06 neels right->atoms.len);
976 3b0f3d61 2020-01-22 neels /* Section before the mid-snake. */
977 3b0f3d61 2020-01-22 neels debug("Section before the mid-snake\n");
979 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[0];
980 3b0f3d61 2020-01-22 neels unsigned int left_section_len = mid_snake.left_start;
981 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[0];
982 3b0f3d61 2020-01-22 neels unsigned int right_section_len = mid_snake.right_start;
984 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
985 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
986 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
987 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
988 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
989 0d27172a 2020-05-06 neels right_atom,
990 0d27172a 2020-05-06 neels right_section_len))
991 3b0f3d61 2020-01-22 neels goto return_rc;
992 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
993 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
994 0d27172a 2020-05-06 neels * "minus" chunk, then. */
995 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
996 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
997 3b0f3d61 2020-01-22 neels right_atom, 0))
998 3b0f3d61 2020-01-22 neels goto return_rc;
999 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
1000 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
1001 0d27172a 2020-05-06 neels * "plus" chunk, then. */
1002 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1003 3b0f3d61 2020-01-22 neels left_atom, 0,
1004 0d27172a 2020-05-06 neels right_atom,
1005 0d27172a 2020-05-06 neels right_section_len))
1006 3b0f3d61 2020-01-22 neels goto return_rc;
1008 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
1009 0d27172a 2020-05-06 neels * nothing before the mid-snake. */
1011 984ca65b 2020-10-11 neels if (mid_snake.left_end > mid_snake.left_start
1012 984ca65b 2020-10-11 neels || mid_snake.right_end > mid_snake.right_start) {
1013 984ca65b 2020-10-11 neels /* The midpoint is a section of identical data on both
1014 984ca65b 2020-10-11 neels * sides, or a certain differing line: that section
1015 984ca65b 2020-10-11 neels * immediately becomes a solved chunk. */
1016 a45330b1 2020-05-05 neels debug("the mid-snake\n");
1017 a45330b1 2020-05-05 neels if (!diff_state_add_chunk(state, true,
1018 0d27172a 2020-05-06 neels &left->atoms.head[mid_snake.left_start],
1019 0d27172a 2020-05-06 neels mid_snake.left_end - mid_snake.left_start,
1020 0d27172a 2020-05-06 neels &right->atoms.head[mid_snake.right_start],
1021 0d27172a 2020-05-06 neels mid_snake.right_end - mid_snake.right_start))
1022 a45330b1 2020-05-05 neels goto return_rc;
1025 3b0f3d61 2020-01-22 neels /* Section after the mid-snake. */
1026 3b0f3d61 2020-01-22 neels debug("Section after the mid-snake\n");
1027 0d27172a 2020-05-06 neels debug(" left_end %u right_end %u\n",
1028 0d27172a 2020-05-06 neels mid_snake.left_end, mid_snake.right_end);
1029 0d27172a 2020-05-06 neels debug(" left_count %u right_count %u\n",
1030 0d27172a 2020-05-06 neels left->atoms.len, right->atoms.len);
1031 3b0f3d61 2020-01-22 neels left_atom = &left->atoms.head[mid_snake.left_end];
1032 3b0f3d61 2020-01-22 neels left_section_len = left->atoms.len - mid_snake.left_end;
1033 3b0f3d61 2020-01-22 neels right_atom = &right->atoms.head[mid_snake.right_end];
1034 3b0f3d61 2020-01-22 neels right_section_len = right->atoms.len - mid_snake.right_end;
1036 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
1037 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
1038 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
1039 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
1040 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1041 0d27172a 2020-05-06 neels right_atom,
1042 0d27172a 2020-05-06 neels right_section_len))
1043 3b0f3d61 2020-01-22 neels goto return_rc;
1044 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
1045 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
1046 0d27172a 2020-05-06 neels * "minus" chunk, then. */
1047 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1048 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1049 3b0f3d61 2020-01-22 neels right_atom, 0))
1050 3b0f3d61 2020-01-22 neels goto return_rc;
1051 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
1052 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
1053 0d27172a 2020-05-06 neels * "plus" chunk, then. */
1054 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1055 3b0f3d61 2020-01-22 neels left_atom, 0,
1056 0d27172a 2020-05-06 neels right_atom,
1057 0d27172a 2020-05-06 neels right_section_len))
1058 3b0f3d61 2020-01-22 neels goto return_rc;
1060 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
1061 0d27172a 2020-05-06 neels * nothing after the mid-snake. */
1064 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
1066 3b0f3d61 2020-01-22 neels return_rc:
1067 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
1068 3b0f3d61 2020-01-22 neels return rc;
1071 0d27172a 2020-05-06 neels /* Myers Diff tracing from the start all the way through to the end, requiring
1072 0d27172a 2020-05-06 neels * quadratic amounts of memory. This can fail if the required space surpasses
1073 0d27172a 2020-05-06 neels * algo_config->permitted_state_size. */
1075 0d27172a 2020-05-06 neels diff_algo_myers(const struct diff_algo_config *algo_config,
1076 0d27172a 2020-05-06 neels struct diff_state *state)
1078 0d27172a 2020-05-06 neels /* do a diff_divide_myers_forward() without a _backward(), so that it
1079 0d27172a 2020-05-06 neels * walks forward across the entire files to reach the end. Keep each
1080 0d27172a 2020-05-06 neels * run's state, and do a final backtrace. */
1081 3e6cba3a 2020-08-13 stsp int rc = ENOMEM;
1082 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
1083 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
1084 8be88dfa 2020-10-21 stsp int *kd_buf;
1086 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
1087 3b0f3d61 2020-01-22 neels debug("left:\n");
1088 3b0f3d61 2020-01-22 neels debug_dump(left);
1089 3b0f3d61 2020-01-22 neels debug("right:\n");
1090 3b0f3d61 2020-01-22 neels debug_dump(right);
1091 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
1093 0d27172a 2020-05-06 neels /* Allocate two columns of a Myers graph, one for the forward and one
1094 0d27172a 2020-05-06 neels * for the backward traversal. */
1095 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
1096 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1 + max;
1097 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len * kd_len;
1098 50198b5f 2020-05-05 neels size_t kd_state_size = kd_buf_size * sizeof(int);
1099 359b29cb 2020-10-11 neels debug("state size: %zu\n", kd_state_size);
1100 3b0f3d61 2020-01-22 neels if (kd_buf_size < kd_len /* overflow? */
1101 f1dbec24 2021-11-23 stsp || (SIZE_MAX / kd_len ) < kd_len
1102 50198b5f 2020-05-05 neels || kd_state_size > algo_config->permitted_state_size) {
1103 3b0f3d61 2020-01-22 neels debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
1104 50198b5f 2020-05-05 neels kd_state_size, algo_config->permitted_state_size);
1105 3b0f3d61 2020-01-22 neels return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1108 8be88dfa 2020-10-21 stsp if (state->kd_buf_size < kd_buf_size) {
1109 8be88dfa 2020-10-21 stsp kd_buf = reallocarray(state->kd_buf, kd_buf_size,
1110 8be88dfa 2020-10-21 stsp sizeof(int));
1111 8be88dfa 2020-10-21 stsp if (!kd_buf)
1112 8be88dfa 2020-10-21 stsp return ENOMEM;
1113 8be88dfa 2020-10-21 stsp state->kd_buf = kd_buf;
1114 8be88dfa 2020-10-21 stsp state->kd_buf_size = kd_buf_size;
1116 8be88dfa 2020-10-21 stsp kd_buf = state->kd_buf;
1119 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
1120 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
1122 0d27172a 2020-05-06 neels /* The 'k' axis in Myers spans positive and negative indexes, so point
1123 0d27172a 2020-05-06 neels * the kd to the middle.
1124 3b0f3d61 2020-01-22 neels * It is then possible to index from -max .. max. */
1125 3b0f3d61 2020-01-22 neels int *kd_origin = kd_buf + max;
1126 3b0f3d61 2020-01-22 neels int *kd_column = kd_origin;
1129 3b0f3d61 2020-01-22 neels int backtrack_d = -1;
1130 3b0f3d61 2020-01-22 neels int backtrack_k = 0;
1132 3b0f3d61 2020-01-22 neels int x, y;
1133 3b0f3d61 2020-01-22 neels for (d = 0; d <= max; d++, kd_column += kd_len) {
1134 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
1136 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
1137 0d27172a 2020-05-06 neels if (k < -(int)right->atoms.len
1138 0d27172a 2020-05-06 neels || k > (int)left->atoms.len) {
1139 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the
1140 0d27172a 2020-05-06 neels * Myers graph, don't calculate it. */
1141 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len)
1142 0d27172a 2020-05-06 neels debug(" %d k <"
1143 0d27172a 2020-05-06 neels " -(int)right->atoms.len %d\n",
1144 0d27172a 2020-05-06 neels k, -(int)right->atoms.len);
1146 0d27172a 2020-05-06 neels debug(" %d k > left->atoms.len %d\n", k,
1147 0d27172a 2020-05-06 neels left->atoms.len);
1148 3b0f3d61 2020-01-22 neels if (k < 0) {
1149 0d27172a 2020-05-06 neels /* We are traversing negatively, and
1150 0d27172a 2020-05-06 neels * already below the entire graph,
1151 0d27172a 2020-05-06 neels * nothing will come of this. */
1152 f579bf77 2020-10-20 neels debug(" break\n");
1155 f579bf77 2020-10-20 neels debug(" continue\n");
1156 3b0f3d61 2020-01-22 neels continue;
1159 3b0f3d61 2020-01-22 neels if (d == 0) {
1160 0d27172a 2020-05-06 neels /* This is the initializing step. There is no
1161 0d27172a 2020-05-06 neels * prev_k yet, get the initial x from the top
1162 0d27172a 2020-05-06 neels * left of the Myers graph. */
1165 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
1167 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring
1168 0d27172a 2020-05-06 neels * moving rightwards in the Myers graph.
1169 0d27172a 2020-05-06 neels * For this, all k should derive from k - 1,
1170 0d27172a 2020-05-06 neels * only the bottom most k derive from k + 1:
1172 3b0f3d61 2020-01-22 neels * | d= 0 1 2
1173 3b0f3d61 2020-01-22 neels * ----+----------------
1175 0d27172a 2020-05-06 neels * 2 | 2,0 <-- from
1176 0d27172a 2020-05-06 neels * | / prev_k = 2 - 1 = 1
1177 3b0f3d61 2020-01-22 neels * 1 | 1,0
1179 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
1181 0d27172a 2020-05-06 neels * -1 | 0,1 <-- bottom most for d=1
1182 0d27172a 2020-05-06 neels * | \\ from prev_k = -1+1 = 0
1183 0d27172a 2020-05-06 neels * -2 | 0,2 <-- bottom most for
1184 0d27172a 2020-05-06 neels * d=2 from
1185 0d27172a 2020-05-06 neels * prev_k = -2+1 = -1
1187 0d27172a 2020-05-06 neels * Except when a k + 1 from a previous run
1188 0d27172a 2020-05-06 neels * already means a further advancement in the
1190 0d27172a 2020-05-06 neels * If k == d, there is no k + 1 and k - 1 is the
1191 0d27172a 2020-05-06 neels * only option.
1192 0d27172a 2020-05-06 neels * If k < d, use k + 1 in case that yields a
1193 0d27172a 2020-05-06 neels * larger x. Also use k + 1 if k - 1 is outside
1194 0d27172a 2020-05-06 neels * the graph.
1196 0d27172a 2020-05-06 neels if (k > -d
1197 0d27172a 2020-05-06 neels && (k == d
1198 0d27172a 2020-05-06 neels || (k - 1 >= -(int)right->atoms.len
1199 0d27172a 2020-05-06 neels && kd_prev_column[k - 1]
1200 0d27172a 2020-05-06 neels >= kd_prev_column[k + 1]))) {
1201 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
1202 0d27172a 2020-05-06 neels * From position prev_k, step to the
1203 0d27172a 2020-05-06 neels * right in the Myers graph: x += 1.
1205 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
1206 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
1207 3b0f3d61 2020-01-22 neels x = prev_x + 1;
1209 3b0f3d61 2020-01-22 neels /* The bottom most one.
1210 0d27172a 2020-05-06 neels * From position prev_k, step to the
1211 0d27172a 2020-05-06 neels * bottom in the Myers graph: y += 1.
1212 0d27172a 2020-05-06 neels * Incrementing y is achieved by
1213 0d27172a 2020-05-06 neels * decrementing k while keeping the same
1214 0d27172a 2020-05-06 neels * x. (since we're deriving y from y =
1215 0d27172a 2020-05-06 neels * x - k).
1217 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
1218 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
1219 3b0f3d61 2020-01-22 neels x = prev_x;
1223 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
1224 0d27172a 2020-05-06 neels while (x < left->atoms.len
1225 b3fb4686 2020-09-20 neels && xk_to_y(x, k) < right->atoms.len) {
1226 b3fb4686 2020-09-20 neels bool same;
1227 b3fb4686 2020-09-20 neels int r = diff_atom_same(&same,
1228 b3fb4686 2020-09-20 neels &left->atoms.head[x],
1229 b3fb4686 2020-09-20 neels &right->atoms.head[
1230 b3fb4686 2020-09-20 neels xk_to_y(x, k)]);
1232 b3fb4686 2020-09-20 neels return r;
1233 b3fb4686 2020-09-20 neels if (!same)
1237 3b0f3d61 2020-01-22 neels kd_column[k] = x;
1239 0d27172a 2020-05-06 neels if (x == left->atoms.len
1240 0d27172a 2020-05-06 neels && xk_to_y(x, k) == right->atoms.len) {
1241 3b0f3d61 2020-01-22 neels /* Found a path */
1242 3b0f3d61 2020-01-22 neels backtrack_d = d;
1243 3b0f3d61 2020-01-22 neels backtrack_k = k;
1244 3b0f3d61 2020-01-22 neels debug("Reached the end at d = %d, k = %d\n",
1245 3b0f3d61 2020-01-22 neels backtrack_d, backtrack_k);
1250 3b0f3d61 2020-01-22 neels if (backtrack_d >= 0)
1254 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
1256 3b0f3d61 2020-01-22 neels /* backtrack. A matrix spanning from start to end of the file is ready:
1258 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
1259 3b0f3d61 2020-01-22 neels * ----+---------------------------------
1263 3b0f3d61 2020-01-22 neels * 2 | 2,0
1265 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
1266 3b0f3d61 2020-01-22 neels * | / / \
1267 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
1268 3b0f3d61 2020-01-22 neels * | \ / \
1269 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
1271 3b0f3d61 2020-01-22 neels * -2 | 0,2
1274 3b0f3d61 2020-01-22 neels * From (4,4) backwards, find the previous position that is the largest, and remember it.
1277 3b0f3d61 2020-01-22 neels for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
1278 3b0f3d61 2020-01-22 neels x = kd_column[k];
1279 3b0f3d61 2020-01-22 neels y = xk_to_y(x, k);
1281 0d27172a 2020-05-06 neels /* When the best position is identified, remember it for that
1282 0d27172a 2020-05-06 neels * kd_column.
1283 0d27172a 2020-05-06 neels * That kd_column is no longer needed otherwise, so just
1284 0d27172a 2020-05-06 neels * re-purpose kd_column[0] = x and kd_column[1] = y,
1285 3b0f3d61 2020-01-22 neels * so that there is no need to allocate more memory.
1287 3b0f3d61 2020-01-22 neels kd_column[0] = x;
1288 3b0f3d61 2020-01-22 neels kd_column[1] = y;
1289 3b0f3d61 2020-01-22 neels debug("Backtrack d=%d: xy=(%d, %d)\n",
1290 3b0f3d61 2020-01-22 neels d, kd_column[0], kd_column[1]);
1292 3b0f3d61 2020-01-22 neels /* Don't access memory before kd_buf */
1293 3b0f3d61 2020-01-22 neels if (d == 0)
1295 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
1297 3b0f3d61 2020-01-22 neels /* When y == 0, backtracking downwards (k-1) is the only way.
1298 3b0f3d61 2020-01-22 neels * When x == 0, backtracking upwards (k+1) is the only way.
1300 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
1301 3b0f3d61 2020-01-22 neels * ----+---------------------------------
1304 3b0f3d61 2020-01-22 neels * | ..y == 0
1305 3b0f3d61 2020-01-22 neels * 2 | 2,0
1307 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
1308 3b0f3d61 2020-01-22 neels * | / / \
1309 0d27172a 2020-05-06 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4,
1310 0d27172a 2020-05-06 neels * | \ / \ backtrack_k = 0
1311 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
1313 3b0f3d61 2020-01-22 neels * -2 | 0,2__
1314 3b0f3d61 2020-01-22 neels * | x == 0
1316 3b0f3d61 2020-01-22 neels if (y == 0
1317 0d27172a 2020-05-06 neels || (x > 0
1318 0d27172a 2020-05-06 neels && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1319 3b0f3d61 2020-01-22 neels k = k - 1;
1320 3b0f3d61 2020-01-22 neels debug("prev k=k-1=%d x=%d y=%d\n",
1321 0d27172a 2020-05-06 neels k, kd_prev_column[k],
1322 0d27172a 2020-05-06 neels xk_to_y(kd_prev_column[k], k));
1324 3b0f3d61 2020-01-22 neels k = k + 1;
1325 3b0f3d61 2020-01-22 neels debug("prev k=k+1=%d x=%d y=%d\n",
1326 0d27172a 2020-05-06 neels k, kd_prev_column[k],
1327 0d27172a 2020-05-06 neels xk_to_y(kd_prev_column[k], k));
1329 3b0f3d61 2020-01-22 neels kd_column = kd_prev_column;
1332 3b0f3d61 2020-01-22 neels /* Forwards again, this time recording the diff chunks.
1333 0d27172a 2020-05-06 neels * Definitely start from 0,0. kd_column[0] may actually point to the
1334 0d27172a 2020-05-06 neels * bottom of a snake starting at 0,0 */
1338 3b0f3d61 2020-01-22 neels kd_column = kd_origin;
1339 3b0f3d61 2020-01-22 neels for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1340 3b0f3d61 2020-01-22 neels int next_x = kd_column[0];
1341 3b0f3d61 2020-01-22 neels int next_y = kd_column[1];
1342 3b0f3d61 2020-01-22 neels debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1343 3b0f3d61 2020-01-22 neels x, y, next_x, next_y);
1345 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[x];
1346 3b0f3d61 2020-01-22 neels int left_section_len = next_x - x;
1347 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[y];
1348 3b0f3d61 2020-01-22 neels int right_section_len = next_y - y;
1350 3e6cba3a 2020-08-13 stsp rc = ENOMEM;
1351 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
1352 3b0f3d61 2020-01-22 neels /* This must be a snake slide.
1353 0d27172a 2020-05-06 neels * Snake slides have a straight line leading into them
1354 0d27172a 2020-05-06 neels * (except when starting at (0,0)). Find out whether the
1355 0d27172a 2020-05-06 neels * lead-in is horizontal or vertical:
1358 3b0f3d61 2020-01-22 neels * ---------->
1360 3b0f3d61 2020-01-22 neels * r| o-o o
1367 0d27172a 2020-05-06 neels * If left_section_len > right_section_len, the lead-in
1368 0d27172a 2020-05-06 neels * is horizontal, meaning first remove one atom from the
1369 0d27172a 2020-05-06 neels * left before sliding down the snake.
1370 0d27172a 2020-05-06 neels * If right_section_len > left_section_len, the lead-in
1371 0d27172a 2020-05-06 neels * is vetical, so add one atom from the right before
1372 0d27172a 2020-05-06 neels * sliding down the snake. */
1373 3b0f3d61 2020-01-22 neels if (left_section_len == right_section_len + 1) {
1374 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1375 3b0f3d61 2020-01-22 neels left_atom, 1,
1376 3b0f3d61 2020-01-22 neels right_atom, 0))
1377 3b0f3d61 2020-01-22 neels goto return_rc;
1378 3b0f3d61 2020-01-22 neels left_atom++;
1379 3b0f3d61 2020-01-22 neels left_section_len--;
1380 3b0f3d61 2020-01-22 neels } else if (right_section_len == left_section_len + 1) {
1381 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1382 3b0f3d61 2020-01-22 neels left_atom, 0,
1383 3b0f3d61 2020-01-22 neels right_atom, 1))
1384 3b0f3d61 2020-01-22 neels goto return_rc;
1385 3b0f3d61 2020-01-22 neels right_atom++;
1386 3b0f3d61 2020-01-22 neels right_section_len--;
1387 3b0f3d61 2020-01-22 neels } else if (left_section_len != right_section_len) {
1388 0d27172a 2020-05-06 neels /* The numbers are making no sense. Should never
1389 0d27172a 2020-05-06 neels * happen. */
1390 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1391 3b0f3d61 2020-01-22 neels goto return_rc;
1394 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1395 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1396 0d27172a 2020-05-06 neels right_atom,
1397 0d27172a 2020-05-06 neels right_section_len))
1398 3b0f3d61 2020-01-22 neels goto return_rc;
1399 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
1400 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
1401 0d27172a 2020-05-06 neels * "minus" chunk, then. */
1402 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1403 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1404 3b0f3d61 2020-01-22 neels right_atom, 0))
1405 3b0f3d61 2020-01-22 neels goto return_rc;
1406 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
1407 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
1408 0d27172a 2020-05-06 neels * "plus" chunk, then. */
1409 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1410 3b0f3d61 2020-01-22 neels left_atom, 0,
1411 0d27172a 2020-05-06 neels right_atom,
1412 0d27172a 2020-05-06 neels right_section_len))
1413 3b0f3d61 2020-01-22 neels goto return_rc;
1416 3b0f3d61 2020-01-22 neels x = next_x;
1417 3b0f3d61 2020-01-22 neels y = next_y;
1420 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
1422 3b0f3d61 2020-01-22 neels return_rc:
1423 3b0f3d61 2020-01-22 neels debug("** END %s rc=%d\n", __func__, rc);
1424 3b0f3d61 2020-01-22 neels return rc;
