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 3b0f3d61 2020-01-22 neels #include <diff/diff_main.h>
22 3b0f3d61 2020-01-22 neels #include "debug.h"
24 3b0f3d61 2020-01-22 neels /* Myers' diff algorithm [1] is nicely explained in [2].
25 3b0f3d61 2020-01-22 neels * [1] http://www.xmailserver.org/diff2.pdf
26 3b0f3d61 2020-01-22 neels * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
28 3b0f3d61 2020-01-22 neels * Myers approaches finding the smallest diff as a graph problem.
29 3b0f3d61 2020-01-22 neels * The crux is that the original algorithm requires quadratic amount of memory:
30 3b0f3d61 2020-01-22 neels * both sides' lengths added, and that squared. So if we're diffing lines of text, two files with 1000 lines each would
31 3b0f3d61 2020-01-22 neels * blow up to a matrix of about 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
32 3b0f3d61 2020-01-22 neels * The solution is using Myers' "divide and conquer" extension algorithm, which does the original traversal from both
33 3b0f3d61 2020-01-22 neels * ends of the files to reach a middle where these "snakes" touch, hence does not need to backtrace the traversal, and
34 3b0f3d61 2020-01-22 neels * so gets away with only keeping a single column of that huge state matrix in memory.
36 3b0f3d61 2020-01-22 neels * Todo: the divide and conquer requires linear *space*, not necessarily linear *time*. It recurses, apparently doing
37 3b0f3d61 2020-01-22 neels * multiple Myers passes, and also it apparently favors fragmented diffs in cases where chunks of text were moved to a
38 3b0f3d61 2020-01-22 neels * different place. Up to a given count of diff atoms (text lines), it might be desirable to accept the quadratic memory
39 3b0f3d61 2020-01-22 neels * usage, get nicer diffs and less re-iteration of the same data?
42 3b0f3d61 2020-01-22 neels struct diff_box {
43 3b0f3d61 2020-01-22 neels unsigned int left_start;
44 3b0f3d61 2020-01-22 neels unsigned int left_end;
45 3b0f3d61 2020-01-22 neels unsigned int right_start;
46 3b0f3d61 2020-01-22 neels unsigned int right_end;
49 3b0f3d61 2020-01-22 neels #define diff_box_empty(DIFF_SNAKE) ((DIFF_SNAKE)->left_end == 0)
52 3b0f3d61 2020-01-22 neels /* If the two contents of a file are A B C D E and X B C Y,
53 3b0f3d61 2020-01-22 neels * the Myers diff graph looks like:
57 3b0f3d61 2020-01-22 neels * k-1 0 1 2 3 4 5
58 3b0f3d61 2020-01-22 neels * \ A B C D E
59 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o-o
60 3b0f3d61 2020-01-22 neels * X | | | | | |
61 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o-o
62 3b0f3d61 2020-01-22 neels * B | |\| | | |
63 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o-o
64 3b0f3d61 2020-01-22 neels * C | | |\| | |
65 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-o-o
66 3b0f3d61 2020-01-22 neels * Y | | | | | |\
67 3b0f3d61 2020-01-22 neels * 4 o-o-o-o-o-o c1
71 3b0f3d61 2020-01-22 neels * Moving right means delete an atom from the left-hand-side,
72 3b0f3d61 2020-01-22 neels * Moving down means add an atom from the right-hand-side.
73 3b0f3d61 2020-01-22 neels * Diagonals indicate identical atoms on both sides, the challenge is to use as many diagonals as possible.
75 3b0f3d61 2020-01-22 neels * The original Myers algorithm walks all the way from the top left to the bottom right, remembers all steps, and then
76 3b0f3d61 2020-01-22 neels * backtraces to find the shortest path. However, that requires keeping the entire graph in memory, which needs
77 3b0f3d61 2020-01-22 neels * quadratic space.
79 3b0f3d61 2020-01-22 neels * Myers adds a variant that uses linear space -- note, not linear time, only linear space: walk forward and backward,
80 3b0f3d61 2020-01-22 neels * find a meeting point in the middle, and recurse on the two separate sections. This is called "divide and conquer".
82 3b0f3d61 2020-01-22 neels * d: the step number, starting with 0, a.k.a. the distance from the starting point.
83 3b0f3d61 2020-01-22 neels * k: relative index in the state array for the forward scan, indicating on which diagonal through the diff graph we
84 3b0f3d61 2020-01-22 neels * currently are.
85 3b0f3d61 2020-01-22 neels * c: relative index in the state array for the backward scan, indicating the diagonal number from the bottom up.
87 3b0f3d61 2020-01-22 neels * The "divide and conquer" traversal through the Myers graph looks like this:
89 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 2 1 0
90 3b0f3d61 2020-01-22 neels * ----+--------------------------------------------
94 3b0f3d61 2020-01-22 neels * 3 | 3,0 5,2 2
96 3b0f3d61 2020-01-22 neels * 2 | 2,0 5,3 1
98 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
99 3b0f3d61 2020-01-22 neels * | / / \ /
100 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 -1
102 3b0f3d61 2020-01-22 neels * -1 | 0,1 1,2 3,4 -2
104 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
107 3b0f3d61 2020-01-22 neels * | forward-> <-backward
109 3b0f3d61 2020-01-22 neels * x,y pairs here are the coordinates in the Myers graph:
110 3b0f3d61 2020-01-22 neels * x = atom index in left-side source, y = atom index in the right-side source.
112 3b0f3d61 2020-01-22 neels * Only one forward column and one backward column are kept in mem, each need at most left.len + 1 + right.len items.
113 3b0f3d61 2020-01-22 neels * Note that each d step occupies either the even or the odd items of a column: if e.g. the previous column is in the
114 3b0f3d61 2020-01-22 neels * odd items, the next column is formed in the even items, without overwriting the previous column's results.
116 3b0f3d61 2020-01-22 neels * Also note that from the diagonal index k and the x coordinate, the y coordinate can be derived:
117 3b0f3d61 2020-01-22 neels * y = x - k
118 3b0f3d61 2020-01-22 neels * Hence the state array only needs to keep the x coordinate, i.e. the position in the left-hand file, and the y
119 3b0f3d61 2020-01-22 neels * coordinate, i.e. position in the right-hand file, is derived from the index in the state array.
121 3b0f3d61 2020-01-22 neels * The two traces meet at 4,3, the first step (here found in the forward traversal) where a forward position is on or
122 3b0f3d61 2020-01-22 neels * past a backward traced position on the same diagonal.
124 3b0f3d61 2020-01-22 neels * This divides the problem space into:
126 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
127 3b0f3d61 2020-01-22 neels * A B C D E
128 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o
129 3b0f3d61 2020-01-22 neels * X | | | | |
130 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o
131 3b0f3d61 2020-01-22 neels * B | |\| | |
132 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o
133 3b0f3d61 2020-01-22 neels * C | | |\| |
134 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-*-o *: forward and backward meet here
138 3b0f3d61 2020-01-22 neels * Doing the same on each section lead to:
140 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
141 3b0f3d61 2020-01-22 neels * A B C D E
144 3b0f3d61 2020-01-22 neels * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
145 3b0f3d61 2020-01-22 neels * B \ f: then forward d=2 reaches here (sliding down the snake)
146 3b0f3d61 2020-01-22 neels * 2 o As result, the box from b to f is found to be identical;
147 3b0f3d61 2020-01-22 neels * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial tail 3,3 to 4,3.
152 3b0f3d61 2020-01-22 neels * 4 o *: forward and backward meet here
154 3b0f3d61 2020-01-22 neels * and solving the last top left box gives:
156 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
157 3b0f3d61 2020-01-22 neels * A B C D E -A
158 3b0f3d61 2020-01-22 neels * 0 o-o +X
170 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))
171 3b0f3d61 2020-01-22 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
172 3b0f3d61 2020-01-22 neels #define k_to_c(K, DELTA) ((K) + (DELTA))
173 3b0f3d61 2020-01-22 neels #define c_to_k(C, DELTA) ((C) - (DELTA))
175 3b0f3d61 2020-01-22 neels /* Do one forwards step in the "divide and conquer" graph traversal.
176 3b0f3d61 2020-01-22 neels * left: the left side to diff.
177 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
178 3b0f3d61 2020-01-22 neels * kd_forward: the traversal state for forwards traversal, modified by this function.
179 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
180 3b0f3d61 2020-01-22 neels * kd_forward points at the center of the state array, allowing negative indexes.
181 3b0f3d61 2020-01-22 neels * kd_backward: the traversal state for backwards traversal, to find a meeting point.
182 3b0f3d61 2020-01-22 neels * Since forwards is done first, kd_backward will be valid for d - 1, not d.
183 3b0f3d61 2020-01-22 neels * kd_backward points at the center of the state array, allowing negative indexes.
184 3b0f3d61 2020-01-22 neels * d: Step or distance counter, indicating for what value of d the kd_forward should be populated.
185 3b0f3d61 2020-01-22 neels * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should be for d == 0.
186 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
188 a45330b1 2020-05-05 neels static bool diff_divide_myers_forward(struct diff_data *left, struct diff_data *right,
189 3b0f3d61 2020-01-22 neels int *kd_forward, int *kd_backward, int d,
190 3b0f3d61 2020-01-22 neels struct diff_box *meeting_snake)
192 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
196 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
198 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
199 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
200 3b0f3d61 2020-01-22 neels /* This diagonal is completely outside of the Myers graph, don't calculate it. */
201 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len)
202 3b0f3d61 2020-01-22 neels debug(" %d k < -(int)right->atoms.len %d\n", k, -(int)right->atoms.len);
204 3b0f3d61 2020-01-22 neels debug(" %d k > left->atoms.len %d\n", k, left->atoms.len);
205 3b0f3d61 2020-01-22 neels if (k < 0) {
206 3b0f3d61 2020-01-22 neels /* We are traversing negatively, and already below the entire graph, nothing will come
207 3b0f3d61 2020-01-22 neels * of this. */
208 3b0f3d61 2020-01-22 neels debug(" break");
211 3b0f3d61 2020-01-22 neels debug(" continue");
214 3b0f3d61 2020-01-22 neels debug("- k = %d\n", k);
215 3b0f3d61 2020-01-22 neels if (d == 0) {
216 3b0f3d61 2020-01-22 neels /* This is the initializing step. There is no prev_k yet, get the initial x from the top left of
217 3b0f3d61 2020-01-22 neels * the Myers graph. */
220 3b0f3d61 2020-01-22 neels /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
221 3b0f3d61 2020-01-22 neels * For this, all k should derive from k - 1, only the bottom most k derive from k + 1:
223 3b0f3d61 2020-01-22 neels * | d= 0 1 2
224 3b0f3d61 2020-01-22 neels * ----+----------------
226 3b0f3d61 2020-01-22 neels * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
230 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
232 3b0f3d61 2020-01-22 neels * -1 | 0,1 <-- bottom most for d=1 from prev_k = -1 + 1 = 0
234 3b0f3d61 2020-01-22 neels * -2 | 0,2 <-- bottom most for d=2 from prev_k = -2 + 1 = -1
236 3b0f3d61 2020-01-22 neels * Except when a k + 1 from a previous run already means a further advancement in the graph.
237 3b0f3d61 2020-01-22 neels * If k == d, there is no k + 1 and k - 1 is the only option.
238 3b0f3d61 2020-01-22 neels * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph.
240 3b0f3d61 2020-01-22 neels else if (k > -d && (k == d
241 3b0f3d61 2020-01-22 neels || (k - 1 >= -(int)right->atoms.len
242 3b0f3d61 2020-01-22 neels && kd_forward[k - 1] >= kd_forward[k + 1]))) {
243 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
244 3b0f3d61 2020-01-22 neels * From position prev_k, step to the right in the Myers graph: x += 1.
246 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
247 f71e8098 2020-05-05 neels int prev_x = kd_forward[prev_k];
248 3b0f3d61 2020-01-22 neels x = prev_x + 1;
250 3b0f3d61 2020-01-22 neels /* The bottom most one.
251 3b0f3d61 2020-01-22 neels * From position prev_k, step to the bottom in the Myers graph: y += 1.
252 3b0f3d61 2020-01-22 neels * Incrementing y is achieved by decrementing k while keeping the same x.
253 3b0f3d61 2020-01-22 neels * (since we're deriving y from y = x - k).
255 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
256 f71e8098 2020-05-05 neels int prev_x = kd_forward[prev_k];
257 3b0f3d61 2020-01-22 neels x = prev_x;
260 f71e8098 2020-05-05 neels int x_before_slide = x;
261 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
262 3b0f3d61 2020-01-22 neels while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len
263 3b0f3d61 2020-01-22 neels && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)]))
265 3b0f3d61 2020-01-22 neels kd_forward[k] = x;
266 c5419a05 2020-05-05 neels if (x_before_slide != x) {
267 c5419a05 2020-05-05 neels debug(" down %d similar lines\n", x - x_before_slide);
270 3b0f3d61 2020-01-22 neels if (DEBUG) {
272 3b0f3d61 2020-01-22 neels for (fi = d; fi >= k; fi--) {
273 3b0f3d61 2020-01-22 neels debug("kd_forward[%d] = (%d, %d)\n", fi, kd_forward[fi], kd_forward[fi] - fi);
275 3b0f3d61 2020-01-22 neels if (kd_forward[fi] >= 0 && kd_forward[fi] < left->atoms.len)
276 3b0f3d61 2020-01-22 neels debug_dump_atom(left, right, &left->atoms.head[kd_forward[fi]]);
278 3b0f3d61 2020-01-22 neels debug("\n");
279 3b0f3d61 2020-01-22 neels if (kd_forward[fi]-fi >= 0 && kd_forward[fi]-fi < right->atoms.len)
280 3b0f3d61 2020-01-22 neels debug_dump_atom(right, left, &right->atoms.head[kd_forward[fi]-fi]);
282 3b0f3d61 2020-01-22 neels debug("\n");
287 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
288 3b0f3d61 2020-01-22 neels || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
291 3b0f3d61 2020-01-22 neels /* Figured out a new forwards traversal, see if this has gone onto or even past a preceding backwards
292 3b0f3d61 2020-01-22 neels * traversal.
294 3b0f3d61 2020-01-22 neels * If the delta in length is odd, then d and backwards_d hit the same state indexes:
295 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
296 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
302 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,3 1
304 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,4<-- 0
306 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,4 -1
308 3b0f3d61 2020-01-22 neels * -1 | 0,1 -2
310 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
313 3b0f3d61 2020-01-22 neels * If the delta is even, they end up off-by-one, i.e. on different diagonals:
315 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
316 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
320 3b0f3d61 2020-01-22 neels * 2 | 2,0 off 2
322 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 1
323 3b0f3d61 2020-01-22 neels * | / // \
324 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4<-- 0
326 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4 -1
328 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
331 3b0f3d61 2020-01-22 neels * So in the forward path, we can only match up diagonals when the delta is odd.
333 fd42ca98 2020-05-05 neels if ((delta & 1) == 0)
335 3b0f3d61 2020-01-22 neels /* Forwards is done first, so the backwards one was still at d - 1. Can't do this for d == 0. */
336 3b0f3d61 2020-01-22 neels int backwards_d = d - 1;
337 fd42ca98 2020-05-05 neels if (backwards_d < 0)
340 fd42ca98 2020-05-05 neels debug("backwards_d = %d\n", backwards_d);
342 fd42ca98 2020-05-05 neels /* If both sides have the same length, forward and backward start on the same diagonal, meaning the
343 fd42ca98 2020-05-05 neels * backwards state index c == k.
344 fd42ca98 2020-05-05 neels * As soon as the lengths are not the same, the backwards traversal starts on a different diagonal, and
345 fd42ca98 2020-05-05 neels * c = k shifted by the difference in length.
347 fd42ca98 2020-05-05 neels int c = k_to_c(k, delta);
349 fd42ca98 2020-05-05 neels /* When the file sizes are very different, the traversal trees start on far distant diagonals.
350 fd42ca98 2020-05-05 neels * They don't necessarily meet straight on. See whether this forward value is on a diagonal that
351 fd42ca98 2020-05-05 neels * is also valid in kd_backward[], and match them if so. */
352 fd42ca98 2020-05-05 neels if (c >= -backwards_d && c <= backwards_d) {
353 fd42ca98 2020-05-05 neels /* Current k is on a diagonal that exists in kd_backward[]. If the two x positions have
354 fd42ca98 2020-05-05 neels * met or passed (forward walked onto or past backward), then we've found a midpoint / a
355 fd42ca98 2020-05-05 neels * mid-box.
357 f71e8098 2020-05-05 neels * When forwards and backwards traversals meet, the endpoints of the mid-snake are
358 f71e8098 2020-05-05 neels * not the two points in kd_forward and kd_backward, but rather the section that
359 f71e8098 2020-05-05 neels * was slid (if any) of the current forward/backward traversal only.
361 f71e8098 2020-05-05 neels * For example:
383 f71e8098 2020-05-05 neels * The forward traversal reached M from the top and slid downwards to A.
384 f71e8098 2020-05-05 neels * The backward traversal already reached X, which is not a straight line from M
385 f71e8098 2020-05-05 neels * anymore, so picking a mid-snake from M to X would yield a mistake.
387 f71e8098 2020-05-05 neels * The correct mid-snake is between M and A. M is where the forward traversal hit
388 f71e8098 2020-05-05 neels * the diagonal that the backward traversal has already passed, and A is what it
389 f71e8098 2020-05-05 neels * reaches when sliding down identical lines.
391 fd42ca98 2020-05-05 neels int backward_x = kd_backward[c];
392 50198b5f 2020-05-05 neels debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
393 50198b5f 2020-05-05 neels k, c, x, xk_to_y(x, k), backward_x, xc_to_y(backward_x, c, delta));
394 f71e8098 2020-05-05 neels if (x >= backward_x) {
395 fd42ca98 2020-05-05 neels *meeting_snake = (struct diff_box){
396 f71e8098 2020-05-05 neels .left_start = x_before_slide,
397 fd42ca98 2020-05-05 neels .left_end = x,
398 f71e8098 2020-05-05 neels .right_start = xc_to_y(x_before_slide, c, delta),
399 fd42ca98 2020-05-05 neels .right_end = xk_to_y(x, k),
401 fd42ca98 2020-05-05 neels debug("HIT x=(%u,%u) - y=(%u,%u)\n",
402 fd42ca98 2020-05-05 neels meeting_snake->left_start,
403 fd42ca98 2020-05-05 neels meeting_snake->right_start,
404 fd42ca98 2020-05-05 neels meeting_snake->left_end,
405 fd42ca98 2020-05-05 neels meeting_snake->right_end);
406 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
407 a45330b1 2020-05-05 neels return true;
412 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
413 a45330b1 2020-05-05 neels return false;
416 3b0f3d61 2020-01-22 neels /* Do one backwards step in the "divide and conquer" graph traversal.
417 3b0f3d61 2020-01-22 neels * left: the left side to diff.
418 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
419 3b0f3d61 2020-01-22 neels * kd_forward: the traversal state for forwards traversal, to find a meeting point.
420 3b0f3d61 2020-01-22 neels * Since forwards is done first, after this, both kd_forward and kd_backward will be valid for d.
421 3b0f3d61 2020-01-22 neels * kd_forward points at the center of the state array, allowing negative indexes.
422 3b0f3d61 2020-01-22 neels * kd_backward: the traversal state for backwards traversal, to find a meeting point.
423 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
424 3b0f3d61 2020-01-22 neels * kd_backward points at the center of the state array, allowing negative indexes.
425 3b0f3d61 2020-01-22 neels * d: Step or distance counter, indicating for what value of d the kd_backward should be populated.
426 3b0f3d61 2020-01-22 neels * Before the first invocation, kd_backward[0] shall point at the bottom right of the Myers graph
427 3b0f3d61 2020-01-22 neels * (left.len, right.len).
428 3b0f3d61 2020-01-22 neels * The first invocation will be for d == 1.
429 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
431 a45330b1 2020-05-05 neels static bool diff_divide_myers_backward(struct diff_data *left, struct diff_data *right,
432 3b0f3d61 2020-01-22 neels int *kd_forward, int *kd_backward, int d,
433 3b0f3d61 2020-01-22 neels struct diff_box *meeting_snake)
435 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
439 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
441 3b0f3d61 2020-01-22 neels for (c = d; c >= -d; c -= 2) {
442 3b0f3d61 2020-01-22 neels if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
443 3b0f3d61 2020-01-22 neels /* This diagonal is completely outside of the Myers graph, don't calculate it. */
444 3b0f3d61 2020-01-22 neels if (c < -(int)left->atoms.len)
445 3b0f3d61 2020-01-22 neels debug(" %d c < -(int)left->atoms.len %d\n", c, -(int)left->atoms.len);
447 3b0f3d61 2020-01-22 neels debug(" %d c > right->atoms.len %d\n", c, right->atoms.len);
448 3b0f3d61 2020-01-22 neels if (c < 0) {
449 3b0f3d61 2020-01-22 neels /* We are traversing negatively, and already below the entire graph, nothing will come
450 3b0f3d61 2020-01-22 neels * of this. */
451 3b0f3d61 2020-01-22 neels debug(" break");
454 3b0f3d61 2020-01-22 neels debug(" continue");
457 3b0f3d61 2020-01-22 neels debug("- c = %d\n", c);
458 3b0f3d61 2020-01-22 neels if (d == 0) {
459 3b0f3d61 2020-01-22 neels /* This is the initializing step. There is no prev_c yet, get the initial x from the bottom
460 3b0f3d61 2020-01-22 neels * right of the Myers graph. */
461 3b0f3d61 2020-01-22 neels x = left->atoms.len;
463 3b0f3d61 2020-01-22 neels /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
464 3b0f3d61 2020-01-22 neels * For this, all c should derive from c - 1, only the bottom most c derive from c + 1:
467 3b0f3d61 2020-01-22 neels * ---------------------------------------------------
471 3b0f3d61 2020-01-22 neels * from prev_c = c - 1 --> 5,2 2
475 3b0f3d61 2020-01-22 neels * 4,3 5,4<-- 0
477 3b0f3d61 2020-01-22 neels * bottom most for d=1 from c + 1 --> 4,4 -1
479 3b0f3d61 2020-01-22 neels * bottom most for d=2 --> 3,4 -2
481 3b0f3d61 2020-01-22 neels * Except when a c + 1 from a previous run already means a further advancement in the graph.
482 3b0f3d61 2020-01-22 neels * If c == d, there is no c + 1 and c - 1 is the only option.
483 3b0f3d61 2020-01-22 neels * If c < d, use c + 1 in case that yields a larger x. Also use c + 1 if c - 1 is outside the graph.
485 3b0f3d61 2020-01-22 neels else if (c > -d && (c == d
486 3b0f3d61 2020-01-22 neels || (c - 1 >= -(int)right->atoms.len
487 3b0f3d61 2020-01-22 neels && kd_backward[c - 1] <= kd_backward[c + 1]))) {
488 3b0f3d61 2020-01-22 neels /* A top one.
489 3b0f3d61 2020-01-22 neels * From position prev_c, step upwards in the Myers graph: y -= 1.
490 3b0f3d61 2020-01-22 neels * Decrementing y is achieved by incrementing c while keeping the same x.
491 3b0f3d61 2020-01-22 neels * (since we're deriving y from y = x - c + delta).
493 3b0f3d61 2020-01-22 neels int prev_c = c - 1;
494 f71e8098 2020-05-05 neels int prev_x = kd_backward[prev_c];
495 3b0f3d61 2020-01-22 neels x = prev_x;
497 3b0f3d61 2020-01-22 neels /* The bottom most one.
498 3b0f3d61 2020-01-22 neels * From position prev_c, step to the left in the Myers graph: x -= 1.
500 3b0f3d61 2020-01-22 neels int prev_c = c + 1;
501 f71e8098 2020-05-05 neels int prev_x = kd_backward[prev_c];
502 3b0f3d61 2020-01-22 neels x = prev_x - 1;
505 09c95394 2020-05-05 neels /* Slide up any snake that we might find here (sections of identical lines on both sides). */
506 3b0f3d61 2020-01-22 neels debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c, delta), xc_to_y(x, c, delta)-1);
507 3b0f3d61 2020-01-22 neels if (x > 0) {
508 3b0f3d61 2020-01-22 neels debug(" l="); debug_dump_atom(left, right, &left->atoms.head[x-1]);
510 3b0f3d61 2020-01-22 neels if (xc_to_y(x, c, delta) > 0) {
511 50198b5f 2020-05-05 neels debug(" r="); debug_dump_atom(right, left, &right->atoms.head[xc_to_y(x, c, delta)-1]);
513 f71e8098 2020-05-05 neels int x_before_slide = x;
514 3b0f3d61 2020-01-22 neels while (x > 0 && xc_to_y(x, c, delta) > 0
515 3b0f3d61 2020-01-22 neels && diff_atom_same(&left->atoms.head[x-1], &right->atoms.head[xc_to_y(x, c, delta)-1]))
517 3b0f3d61 2020-01-22 neels kd_backward[c] = x;
518 c5419a05 2020-05-05 neels if (x_before_slide != x) {
519 c5419a05 2020-05-05 neels debug(" up %d similar lines\n", x_before_slide - x);
522 3b0f3d61 2020-01-22 neels if (DEBUG) {
524 3b0f3d61 2020-01-22 neels for (fi = d; fi >= c; fi--) {
525 3b0f3d61 2020-01-22 neels debug("kd_backward[%d] = (%d, %d)\n", fi, kd_backward[fi],
526 3b0f3d61 2020-01-22 neels kd_backward[fi] - fi + delta);
528 3b0f3d61 2020-01-22 neels if (kd_backward[fi] >= 0 && kd_backward[fi] < left->atoms.len)
529 3b0f3d61 2020-01-22 neels debug_dump_atom(left, right, &left->atoms.head[kd_backward[fi]]);
531 3b0f3d61 2020-01-22 neels debug("\n");
532 3b0f3d61 2020-01-22 neels if (kd_backward[fi]-fi+delta >= 0 && kd_backward[fi]-fi+delta < right->atoms.len)
533 3b0f3d61 2020-01-22 neels debug_dump_atom(right, left, &right->atoms.head[kd_backward[fi]-fi+delta]);
535 3b0f3d61 2020-01-22 neels debug("\n");
540 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
541 3b0f3d61 2020-01-22 neels || xc_to_y(x, c, delta) < 0 || xc_to_y(x, c, delta) > right->atoms.len)
544 3b0f3d61 2020-01-22 neels /* Figured out a new backwards traversal, see if this has gone onto or even past a preceding forwards
545 3b0f3d61 2020-01-22 neels * traversal.
547 3b0f3d61 2020-01-22 neels * If the delta in length is even, then d and backwards_d hit the same state indexes -- note how this is
548 3b0f3d61 2020-01-22 neels * different from in the forwards traversal, because now both d are the same:
550 3b0f3d61 2020-01-22 neels * | d= 0 1 2 2 1 0
551 3b0f3d61 2020-01-22 neels * ----+---------------- --------------------
557 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,2 2
559 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,3 1
561 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,3 5,4<-- 0
563 3b0f3d61 2020-01-22 neels * -1 | 0,1 4,4 -1
565 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
568 3b0f3d61 2020-01-22 neels * If the delta is odd, they end up off-by-one, i.e. on different diagonals.
569 3b0f3d61 2020-01-22 neels * So in the backward path, we can only match up diagonals when the delta is even.
571 3b0f3d61 2020-01-22 neels if ((delta & 1) == 0) {
572 3b0f3d61 2020-01-22 neels /* Forwards was done first, now both d are the same. */
573 3b0f3d61 2020-01-22 neels int forwards_d = d;
575 3b0f3d61 2020-01-22 neels /* As soon as the lengths are not the same, the backwards traversal starts on a different diagonal, and
576 3b0f3d61 2020-01-22 neels * c = k shifted by the difference in length.
578 3b0f3d61 2020-01-22 neels int k = c_to_k(c, delta);
580 3b0f3d61 2020-01-22 neels /* When the file sizes are very different, the traversal trees start on far distant diagonals.
581 3b0f3d61 2020-01-22 neels * They don't necessarily meet straight on. See whether this backward value is also on a valid
582 3b0f3d61 2020-01-22 neels * diagonal in kd_forward[], and match them if so. */
583 3b0f3d61 2020-01-22 neels if (k >= -forwards_d && k <= forwards_d) {
584 3b0f3d61 2020-01-22 neels /* Current c is on a diagonal that exists in kd_forward[]. If the two x positions have
585 3b0f3d61 2020-01-22 neels * met or passed (backward walked onto or past forward), then we've found a midpoint / a
586 f71e8098 2020-05-05 neels * mid-box.
588 f71e8098 2020-05-05 neels * When forwards and backwards traversals meet, the endpoints of the mid-snake are
589 f71e8098 2020-05-05 neels * not the two points in kd_forward and kd_backward, but rather the section that
590 f71e8098 2020-05-05 neels * was slid (if any) of the current forward/backward traversal only.
592 f71e8098 2020-05-05 neels * For example:
612 f71e8098 2020-05-05 neels * The backward traversal reached M from the bottom and slid upwards.
613 f71e8098 2020-05-05 neels * The forward traversal already reached X, which is not a straight line from M
614 f71e8098 2020-05-05 neels * anymore, so picking a mid-snake from M to X would yield a mistake.
616 f71e8098 2020-05-05 neels * The correct mid-snake is between M and A. M is where the backward traversal hit
617 f71e8098 2020-05-05 neels * the diagonal that the forwards traversal has already passed, and A is what it
618 f71e8098 2020-05-05 neels * reaches when sliding up identical lines.
621 3b0f3d61 2020-01-22 neels int forward_x = kd_forward[k];
622 50198b5f 2020-05-05 neels debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
623 50198b5f 2020-05-05 neels k, c, forward_x, xk_to_y(forward_x, k), x, xc_to_y(x, c, delta));
624 f71e8098 2020-05-05 neels if (forward_x >= x) {
625 3b0f3d61 2020-01-22 neels *meeting_snake = (struct diff_box){
626 3b0f3d61 2020-01-22 neels .left_start = x,
627 f71e8098 2020-05-05 neels .left_end = x_before_slide,
628 3b0f3d61 2020-01-22 neels .right_start = xc_to_y(x, c, delta),
629 f71e8098 2020-05-05 neels .right_end = xk_to_y(x_before_slide, k),
631 3b0f3d61 2020-01-22 neels debug("HIT x=%u,%u - y=%u,%u\n",
632 3b0f3d61 2020-01-22 neels meeting_snake->left_start,
633 3b0f3d61 2020-01-22 neels meeting_snake->right_start,
634 3b0f3d61 2020-01-22 neels meeting_snake->left_end,
635 3b0f3d61 2020-01-22 neels meeting_snake->right_end);
636 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
637 a45330b1 2020-05-05 neels return true;
642 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
643 a45330b1 2020-05-05 neels return false;
646 3b0f3d61 2020-01-22 neels /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides
647 3b0f3d61 2020-01-22 neels * the problem into smaller chunks. Requires only linear amounts of memory. */
648 3b0f3d61 2020-01-22 neels enum diff_rc diff_algo_myers_divide(const struct diff_algo_config *algo_config, struct diff_state *state)
650 3b0f3d61 2020-01-22 neels enum diff_rc rc = DIFF_RC_ENOMEM;
651 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
652 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
654 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
655 3b0f3d61 2020-01-22 neels debug("left:\n");
656 3b0f3d61 2020-01-22 neels debug_dump(left);
657 3b0f3d61 2020-01-22 neels debug("right:\n");
658 3b0f3d61 2020-01-22 neels debug_dump(right);
659 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
661 3b0f3d61 2020-01-22 neels /* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
662 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
663 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1;
664 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len << 1;
665 3b0f3d61 2020-01-22 neels int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
666 3b0f3d61 2020-01-22 neels if (!kd_buf)
667 3b0f3d61 2020-01-22 neels return DIFF_RC_ENOMEM;
669 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
670 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
671 3b0f3d61 2020-01-22 neels int *kd_forward = kd_buf;
672 3b0f3d61 2020-01-22 neels int *kd_backward = kd_buf + kd_len;
674 3b0f3d61 2020-01-22 neels /* The 'k' axis in Myers spans positive and negative indexes, so point the kd to the middle.
675 3b0f3d61 2020-01-22 neels * It is then possible to index from -max/2 .. max/2. */
676 3b0f3d61 2020-01-22 neels kd_forward += max/2;
677 3b0f3d61 2020-01-22 neels kd_backward += max/2;
680 3b0f3d61 2020-01-22 neels struct diff_box mid_snake = {};
681 a45330b1 2020-05-05 neels bool found_midpoint = false;
682 3b0f3d61 2020-01-22 neels for (d = 0; d <= (max/2); d++) {
683 3b0f3d61 2020-01-22 neels debug("-- d=%d\n", d);
684 a45330b1 2020-05-05 neels found_midpoint = diff_divide_myers_forward(left, right, kd_forward, kd_backward, d, &mid_snake);
685 a45330b1 2020-05-05 neels if (found_midpoint)
687 a45330b1 2020-05-05 neels found_midpoint = diff_divide_myers_backward(left, right, kd_forward, kd_backward, d, &mid_snake);
688 a45330b1 2020-05-05 neels if (found_midpoint)
692 a45330b1 2020-05-05 neels if (!found_midpoint) {
693 3b0f3d61 2020-01-22 neels /* Divide and conquer failed to find a meeting point. Use the fallback_algo defined in the algo_config
694 3b0f3d61 2020-01-22 neels * (leave this to the caller). This is just paranoia/sanity, we normally should always find a midpoint.
696 3b0f3d61 2020-01-22 neels debug(" no midpoint \n");
697 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
698 3b0f3d61 2020-01-22 neels goto return_rc;
700 3b0f3d61 2020-01-22 neels debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
701 3b0f3d61 2020-01-22 neels mid_snake.left_start, mid_snake.left_end, left->atoms.len,
702 3b0f3d61 2020-01-22 neels mid_snake.right_start, mid_snake.right_end, right->atoms.len);
704 3b0f3d61 2020-01-22 neels /* Section before the mid-snake. */
705 3b0f3d61 2020-01-22 neels debug("Section before the mid-snake\n");
707 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[0];
708 3b0f3d61 2020-01-22 neels unsigned int left_section_len = mid_snake.left_start;
709 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[0];
710 3b0f3d61 2020-01-22 neels unsigned int right_section_len = mid_snake.right_start;
712 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
713 3b0f3d61 2020-01-22 neels /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
714 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
715 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
716 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
717 3b0f3d61 2020-01-22 neels goto return_rc;
718 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
719 3b0f3d61 2020-01-22 neels /* Only left atoms and none on the right, they form a "minus" chunk, then. */
720 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
721 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
722 3b0f3d61 2020-01-22 neels right_atom, 0))
723 3b0f3d61 2020-01-22 neels goto return_rc;
724 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
725 3b0f3d61 2020-01-22 neels /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
726 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
727 3b0f3d61 2020-01-22 neels left_atom, 0,
728 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
729 3b0f3d61 2020-01-22 neels goto return_rc;
731 3b0f3d61 2020-01-22 neels /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing before the mid-snake. */
733 a45330b1 2020-05-05 neels if (!diff_box_empty(&mid_snake)) {
734 a45330b1 2020-05-05 neels /* The midpoint is a "snake", i.e. on a section of identical data on both sides: that
735 a45330b1 2020-05-05 neels * section immediately becomes a solved diff chunk. */
736 a45330b1 2020-05-05 neels debug("the mid-snake\n");
737 a45330b1 2020-05-05 neels if (!diff_state_add_chunk(state, true,
738 a45330b1 2020-05-05 neels &left->atoms.head[mid_snake.left_start],
739 a45330b1 2020-05-05 neels mid_snake.left_end - mid_snake.left_start,
740 a45330b1 2020-05-05 neels &right->atoms.head[mid_snake.right_start],
741 a45330b1 2020-05-05 neels mid_snake.right_end - mid_snake.right_start))
742 a45330b1 2020-05-05 neels goto return_rc;
745 3b0f3d61 2020-01-22 neels /* Section after the mid-snake. */
746 3b0f3d61 2020-01-22 neels debug("Section after the mid-snake\n");
747 3b0f3d61 2020-01-22 neels debug(" left_end %u right_end %u\n", mid_snake.left_end, mid_snake.right_end);
748 3b0f3d61 2020-01-22 neels debug(" left_count %u right_count %u\n", left->atoms.len, right->atoms.len);
749 3b0f3d61 2020-01-22 neels left_atom = &left->atoms.head[mid_snake.left_end];
750 3b0f3d61 2020-01-22 neels left_section_len = left->atoms.len - mid_snake.left_end;
751 3b0f3d61 2020-01-22 neels right_atom = &right->atoms.head[mid_snake.right_end];
752 3b0f3d61 2020-01-22 neels right_section_len = right->atoms.len - mid_snake.right_end;
754 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
755 3b0f3d61 2020-01-22 neels /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
756 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
757 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
758 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
759 3b0f3d61 2020-01-22 neels goto return_rc;
760 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
761 3b0f3d61 2020-01-22 neels /* Only left atoms and none on the right, they form a "minus" chunk, then. */
762 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
763 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
764 3b0f3d61 2020-01-22 neels right_atom, 0))
765 3b0f3d61 2020-01-22 neels goto return_rc;
766 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
767 3b0f3d61 2020-01-22 neels /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
768 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
769 3b0f3d61 2020-01-22 neels left_atom, 0,
770 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
771 3b0f3d61 2020-01-22 neels goto return_rc;
773 3b0f3d61 2020-01-22 neels /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing after the mid-snake. */
776 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
778 3b0f3d61 2020-01-22 neels return_rc:
779 3b0f3d61 2020-01-22 neels free(kd_buf);
780 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
781 3b0f3d61 2020-01-22 neels return rc;
784 3b0f3d61 2020-01-22 neels /* Myers Diff tracing from the start all the way through to the end, requiring quadratic amounts of memory. This can
785 3b0f3d61 2020-01-22 neels * fail if the required space surpasses algo_config->permitted_state_size. */
786 3b0f3d61 2020-01-22 neels enum diff_rc diff_algo_myers(const struct diff_algo_config *algo_config, struct diff_state *state)
788 3b0f3d61 2020-01-22 neels /* do a diff_divide_myers_forward() without a _backward(), so that it walks forward across the entire
789 3b0f3d61 2020-01-22 neels * files to reach the end. Keep each run's state, and do a final backtrace. */
790 3b0f3d61 2020-01-22 neels enum diff_rc rc = DIFF_RC_ENOMEM;
791 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
792 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
794 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
795 3b0f3d61 2020-01-22 neels debug("left:\n");
796 3b0f3d61 2020-01-22 neels debug_dump(left);
797 3b0f3d61 2020-01-22 neels debug("right:\n");
798 3b0f3d61 2020-01-22 neels debug_dump(right);
799 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
801 3b0f3d61 2020-01-22 neels /* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
802 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
803 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1 + max;
804 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len * kd_len;
805 50198b5f 2020-05-05 neels size_t kd_state_size = kd_buf_size * sizeof(int);
806 3b0f3d61 2020-01-22 neels debug("state size: %zu\n", kd_buf_size);
807 3b0f3d61 2020-01-22 neels if (kd_buf_size < kd_len /* overflow? */
808 50198b5f 2020-05-05 neels || kd_state_size > algo_config->permitted_state_size) {
809 3b0f3d61 2020-01-22 neels debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
810 50198b5f 2020-05-05 neels kd_state_size, algo_config->permitted_state_size);
811 3b0f3d61 2020-01-22 neels return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
814 3b0f3d61 2020-01-22 neels int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
815 3b0f3d61 2020-01-22 neels if (!kd_buf)
816 3b0f3d61 2020-01-22 neels return DIFF_RC_ENOMEM;
818 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
819 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
821 3b0f3d61 2020-01-22 neels /* The 'k' axis in Myers spans positive and negative indexes, so point the kd to the middle.
822 3b0f3d61 2020-01-22 neels * It is then possible to index from -max .. max. */
823 3b0f3d61 2020-01-22 neels int *kd_origin = kd_buf + max;
824 3b0f3d61 2020-01-22 neels int *kd_column = kd_origin;
827 3b0f3d61 2020-01-22 neels int backtrack_d = -1;
828 3b0f3d61 2020-01-22 neels int backtrack_k = 0;
831 3b0f3d61 2020-01-22 neels for (d = 0; d <= max; d++, kd_column += kd_len) {
832 3b0f3d61 2020-01-22 neels debug("-- d=%d\n", d);
834 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
836 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
837 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
838 3b0f3d61 2020-01-22 neels /* This diagonal is completely outside of the Myers graph, don't calculate it. */
839 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len)
840 3b0f3d61 2020-01-22 neels debug(" %d k < -(int)right->atoms.len %d\n", k, -(int)right->atoms.len);
842 3b0f3d61 2020-01-22 neels debug(" %d k > left->atoms.len %d\n", k, left->atoms.len);
843 3b0f3d61 2020-01-22 neels if (k < 0) {
844 3b0f3d61 2020-01-22 neels /* We are traversing negatively, and already below the entire graph, nothing will come
845 3b0f3d61 2020-01-22 neels * of this. */
846 3b0f3d61 2020-01-22 neels debug(" break");
849 3b0f3d61 2020-01-22 neels debug(" continue");
853 3b0f3d61 2020-01-22 neels debug("- k = %d\n", k);
854 3b0f3d61 2020-01-22 neels if (d == 0) {
855 3b0f3d61 2020-01-22 neels /* This is the initializing step. There is no prev_k yet, get the initial x from the top left of
856 3b0f3d61 2020-01-22 neels * the Myers graph. */
859 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
861 3b0f3d61 2020-01-22 neels /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
862 3b0f3d61 2020-01-22 neels * For this, all k should derive from k - 1, only the bottom most k derive from k + 1:
864 3b0f3d61 2020-01-22 neels * | d= 0 1 2
865 3b0f3d61 2020-01-22 neels * ----+----------------
867 3b0f3d61 2020-01-22 neels * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
871 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
873 3b0f3d61 2020-01-22 neels * -1 | 0,1 <-- bottom most for d=1 from prev_k = -1 + 1 = 0
875 3b0f3d61 2020-01-22 neels * -2 | 0,2 <-- bottom most for d=2 from prev_k = -2 + 1 = -1
877 3b0f3d61 2020-01-22 neels * Except when a k + 1 from a previous run already means a further advancement in the graph.
878 3b0f3d61 2020-01-22 neels * If k == d, there is no k + 1 and k - 1 is the only option.
879 3b0f3d61 2020-01-22 neels * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph.
881 3b0f3d61 2020-01-22 neels if (k > -d && (k == d
882 3b0f3d61 2020-01-22 neels || (k - 1 >= -(int)right->atoms.len
883 3b0f3d61 2020-01-22 neels && kd_prev_column[k - 1] >= kd_prev_column[k + 1]))) {
884 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
885 3b0f3d61 2020-01-22 neels * From position prev_k, step to the right in the Myers graph: x += 1.
887 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
888 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
889 3b0f3d61 2020-01-22 neels x = prev_x + 1;
891 3b0f3d61 2020-01-22 neels /* The bottom most one.
892 3b0f3d61 2020-01-22 neels * From position prev_k, step to the bottom in the Myers graph: y += 1.
893 3b0f3d61 2020-01-22 neels * Incrementing y is achieved by decrementing k while keeping the same x.
894 3b0f3d61 2020-01-22 neels * (since we're deriving y from y = x - k).
896 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
897 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
898 3b0f3d61 2020-01-22 neels x = prev_x;
902 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
903 3b0f3d61 2020-01-22 neels while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len
904 3b0f3d61 2020-01-22 neels && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)]))
906 3b0f3d61 2020-01-22 neels kd_column[k] = x;
908 3b0f3d61 2020-01-22 neels if (DEBUG) {
910 3b0f3d61 2020-01-22 neels for (fi = d; fi >= k; fi-=2) {
911 3b0f3d61 2020-01-22 neels debug("kd_column[%d] = (%d, %d)\n", fi, kd_column[fi], kd_column[fi] - fi);
913 3b0f3d61 2020-01-22 neels if (kd_column[fi] >= 0 && kd_column[fi] < left->atoms.len)
914 3b0f3d61 2020-01-22 neels debug_dump_atom(left, right, &left->atoms.head[kd_column[fi]]);
916 3b0f3d61 2020-01-22 neels debug("\n");
917 3b0f3d61 2020-01-22 neels if (kd_column[fi]-fi >= 0 && kd_column[fi]-fi < right->atoms.len)
918 3b0f3d61 2020-01-22 neels debug_dump_atom(right, left, &right->atoms.head[kd_column[fi]-fi]);
920 3b0f3d61 2020-01-22 neels debug("\n");
925 3b0f3d61 2020-01-22 neels if (x == left->atoms.len && xk_to_y(x, k) == right->atoms.len) {
926 3b0f3d61 2020-01-22 neels /* Found a path */
927 3b0f3d61 2020-01-22 neels backtrack_d = d;
928 3b0f3d61 2020-01-22 neels backtrack_k = k;
929 3b0f3d61 2020-01-22 neels debug("Reached the end at d = %d, k = %d\n",
930 3b0f3d61 2020-01-22 neels backtrack_d, backtrack_k);
935 3b0f3d61 2020-01-22 neels if (backtrack_d >= 0)
939 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
941 3b0f3d61 2020-01-22 neels /* backtrack. A matrix spanning from start to end of the file is ready:
943 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
944 3b0f3d61 2020-01-22 neels * ----+---------------------------------
950 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
952 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
954 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
956 3b0f3d61 2020-01-22 neels * -2 | 0,2
959 3b0f3d61 2020-01-22 neels * From (4,4) backwards, find the previous position that is the largest, and remember it.
962 3b0f3d61 2020-01-22 neels for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
963 3b0f3d61 2020-01-22 neels x = kd_column[k];
964 3b0f3d61 2020-01-22 neels y = xk_to_y(x, k);
966 3b0f3d61 2020-01-22 neels /* When the best position is identified, remember it for that kd_column.
967 3b0f3d61 2020-01-22 neels * That kd_column is no longer needed otherwise, so just re-purpose kd_column[0] = x and kd_column[1] = y,
968 3b0f3d61 2020-01-22 neels * so that there is no need to allocate more memory.
970 3b0f3d61 2020-01-22 neels kd_column[0] = x;
971 3b0f3d61 2020-01-22 neels kd_column[1] = y;
972 3b0f3d61 2020-01-22 neels debug("Backtrack d=%d: xy=(%d, %d)\n",
973 3b0f3d61 2020-01-22 neels d, kd_column[0], kd_column[1]);
975 3b0f3d61 2020-01-22 neels /* Don't access memory before kd_buf */
976 3b0f3d61 2020-01-22 neels if (d == 0)
978 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
980 3b0f3d61 2020-01-22 neels /* When y == 0, backtracking downwards (k-1) is the only way.
981 3b0f3d61 2020-01-22 neels * When x == 0, backtracking upwards (k+1) is the only way.
983 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
984 3b0f3d61 2020-01-22 neels * ----+---------------------------------
987 3b0f3d61 2020-01-22 neels * | ..y == 0
990 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
992 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
994 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
996 3b0f3d61 2020-01-22 neels * -2 | 0,2__
997 3b0f3d61 2020-01-22 neels * | x == 0
999 3b0f3d61 2020-01-22 neels debug("prev[k-1] = %d,%d prev[k+1] = %d,%d\n",
1000 3b0f3d61 2020-01-22 neels kd_prev_column[k-1], xk_to_y(kd_prev_column[k-1],k-1),
1001 3b0f3d61 2020-01-22 neels kd_prev_column[k+1], xk_to_y(kd_prev_column[k+1],k+1));
1002 3b0f3d61 2020-01-22 neels if (y == 0
1003 3b0f3d61 2020-01-22 neels || (x > 0 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1004 3b0f3d61 2020-01-22 neels k = k - 1;
1005 3b0f3d61 2020-01-22 neels debug("prev k=k-1=%d x=%d y=%d\n",
1006 3b0f3d61 2020-01-22 neels k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k));
1008 3b0f3d61 2020-01-22 neels k = k + 1;
1009 3b0f3d61 2020-01-22 neels debug("prev k=k+1=%d x=%d y=%d\n",
1010 3b0f3d61 2020-01-22 neels k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k));
1012 3b0f3d61 2020-01-22 neels kd_column = kd_prev_column;
1015 3b0f3d61 2020-01-22 neels /* Forwards again, this time recording the diff chunks.
1016 3b0f3d61 2020-01-22 neels * Definitely start from 0,0. kd_column[0] may actually point to the bottom of a snake starting at 0,0 */
1020 3b0f3d61 2020-01-22 neels kd_column = kd_origin;
1021 3b0f3d61 2020-01-22 neels for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1022 3b0f3d61 2020-01-22 neels int next_x = kd_column[0];
1023 3b0f3d61 2020-01-22 neels int next_y = kd_column[1];
1024 3b0f3d61 2020-01-22 neels debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1025 3b0f3d61 2020-01-22 neels x, y, next_x, next_y);
1027 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[x];
1028 3b0f3d61 2020-01-22 neels int left_section_len = next_x - x;
1029 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[y];
1030 3b0f3d61 2020-01-22 neels int right_section_len = next_y - y;
1032 3b0f3d61 2020-01-22 neels rc = DIFF_RC_ENOMEM;
1033 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
1034 3b0f3d61 2020-01-22 neels /* This must be a snake slide.
1035 3b0f3d61 2020-01-22 neels * Snake slides have a straight line leading into them (except when starting at (0,0)). Find
1036 3b0f3d61 2020-01-22 neels * out whether the lead-in is horizontal or vertical:
1039 3b0f3d61 2020-01-22 neels * ---------->
1041 3b0f3d61 2020-01-22 neels * r| o-o o
1048 3b0f3d61 2020-01-22 neels * If left_section_len > right_section_len, the lead-in is horizontal, meaning first
1049 3b0f3d61 2020-01-22 neels * remove one atom from the left before sliding down the snake.
1050 3b0f3d61 2020-01-22 neels * If right_section_len > left_section_len, the lead-in is vetical, so add one atom from
1051 3b0f3d61 2020-01-22 neels * the right before sliding down the snake. */
1052 3b0f3d61 2020-01-22 neels if (left_section_len == right_section_len + 1) {
1053 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1054 3b0f3d61 2020-01-22 neels left_atom, 1,
1055 3b0f3d61 2020-01-22 neels right_atom, 0))
1056 3b0f3d61 2020-01-22 neels goto return_rc;
1057 3b0f3d61 2020-01-22 neels left_atom++;
1058 3b0f3d61 2020-01-22 neels left_section_len--;
1059 3b0f3d61 2020-01-22 neels } else if (right_section_len == left_section_len + 1) {
1060 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1061 3b0f3d61 2020-01-22 neels left_atom, 0,
1062 3b0f3d61 2020-01-22 neels right_atom, 1))
1063 3b0f3d61 2020-01-22 neels goto return_rc;
1064 3b0f3d61 2020-01-22 neels right_atom++;
1065 3b0f3d61 2020-01-22 neels right_section_len--;
1066 3b0f3d61 2020-01-22 neels } else if (left_section_len != right_section_len) {
1067 3b0f3d61 2020-01-22 neels /* The numbers are making no sense. Should never happen. */
1068 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1069 3b0f3d61 2020-01-22 neels goto return_rc;
1072 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1073 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1074 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
1075 3b0f3d61 2020-01-22 neels goto return_rc;
1076 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
1077 3b0f3d61 2020-01-22 neels /* Only left atoms and none on the right, they form a "minus" chunk, then. */
1078 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1079 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1080 3b0f3d61 2020-01-22 neels right_atom, 0))
1081 3b0f3d61 2020-01-22 neels goto return_rc;
1082 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
1083 3b0f3d61 2020-01-22 neels /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
1084 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1085 3b0f3d61 2020-01-22 neels left_atom, 0,
1086 3b0f3d61 2020-01-22 neels right_atom, right_section_len))
1087 3b0f3d61 2020-01-22 neels goto return_rc;
1090 3b0f3d61 2020-01-22 neels x = next_x;
1091 3b0f3d61 2020-01-22 neels y = next_y;
1094 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
1096 3b0f3d61 2020-01-22 neels return_rc:
1097 3b0f3d61 2020-01-22 neels free(kd_buf);
1098 3b0f3d61 2020-01-22 neels debug("** END %s rc=%d\n", __func__, rc);
1099 3b0f3d61 2020-01-22 neels return rc;
