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 0d27172a 2020-05-06 neels * both sides' lengths added, and that squared. So if we're diffing lines of
31 0d27172a 2020-05-06 neels * text, two files with 1000 lines each would blow up to a matrix of about
32 0d27172a 2020-05-06 neels * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
33 0d27172a 2020-05-06 neels * The solution is using Myers' "divide and conquer" extension algorithm, which
34 0d27172a 2020-05-06 neels * does the original traversal from both ends of the files to reach a middle
35 0d27172a 2020-05-06 neels * where these "snakes" touch, hence does not need to backtrace the traversal,
36 0d27172a 2020-05-06 neels * and so gets away with only keeping a single column of that huge state matrix
37 0d27172a 2020-05-06 neels * in memory.
40 3b0f3d61 2020-01-22 neels struct diff_box {
41 3b0f3d61 2020-01-22 neels unsigned int left_start;
42 3b0f3d61 2020-01-22 neels unsigned int left_end;
43 3b0f3d61 2020-01-22 neels unsigned int right_start;
44 3b0f3d61 2020-01-22 neels unsigned int right_end;
47 3b0f3d61 2020-01-22 neels #define diff_box_empty(DIFF_SNAKE) ((DIFF_SNAKE)->left_end == 0)
50 3b0f3d61 2020-01-22 neels /* If the two contents of a file are A B C D E and X B C Y,
51 3b0f3d61 2020-01-22 neels * the Myers diff graph looks like:
55 3b0f3d61 2020-01-22 neels * k-1 0 1 2 3 4 5
56 3b0f3d61 2020-01-22 neels * \ A B C D E
57 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o-o
58 3b0f3d61 2020-01-22 neels * X | | | | | |
59 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o-o
60 3b0f3d61 2020-01-22 neels * B | |\| | | |
61 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o-o
62 3b0f3d61 2020-01-22 neels * C | | |\| | |
63 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-o-o
64 3b0f3d61 2020-01-22 neels * Y | | | | | |\
65 3b0f3d61 2020-01-22 neels * 4 o-o-o-o-o-o c1
69 3b0f3d61 2020-01-22 neels * Moving right means delete an atom from the left-hand-side,
70 3b0f3d61 2020-01-22 neels * Moving down means add an atom from the right-hand-side.
71 0d27172a 2020-05-06 neels * Diagonals indicate identical atoms on both sides, the challenge is to use as
72 0d27172a 2020-05-06 neels * many diagonals as possible.
74 0d27172a 2020-05-06 neels * The original Myers algorithm walks all the way from the top left to the
75 0d27172a 2020-05-06 neels * bottom right, remembers all steps, and then backtraces to find the shortest
76 0d27172a 2020-05-06 neels * path. However, that requires keeping the entire graph in memory, which needs
77 3b0f3d61 2020-01-22 neels * quadratic space.
79 0d27172a 2020-05-06 neels * Myers adds a variant that uses linear space -- note, not linear time, only
80 0d27172a 2020-05-06 neels * linear space: walk forward and backward, find a meeting point in the middle,
81 0d27172a 2020-05-06 neels * and recurse on the two separate sections. This is called "divide and
82 0d27172a 2020-05-06 neels * conquer".
84 0d27172a 2020-05-06 neels * d: the step number, starting with 0, a.k.a. the distance from the starting
86 0d27172a 2020-05-06 neels * k: relative index in the state array for the forward scan, indicating on
87 0d27172a 2020-05-06 neels * which diagonal through the diff graph we currently are.
88 0d27172a 2020-05-06 neels * c: relative index in the state array for the backward scan, indicating the
89 0d27172a 2020-05-06 neels * diagonal number from the bottom up.
91 3b0f3d61 2020-01-22 neels * The "divide and conquer" traversal through the Myers graph looks like this:
93 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 2 1 0
94 3b0f3d61 2020-01-22 neels * ----+--------------------------------------------
98 3b0f3d61 2020-01-22 neels * 3 | 3,0 5,2 2
100 3b0f3d61 2020-01-22 neels * 2 | 2,0 5,3 1
102 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
103 3b0f3d61 2020-01-22 neels * | / / \ /
104 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 -1
106 3b0f3d61 2020-01-22 neels * -1 | 0,1 1,2 3,4 -2
108 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
111 3b0f3d61 2020-01-22 neels * | forward-> <-backward
113 3b0f3d61 2020-01-22 neels * x,y pairs here are the coordinates in the Myers graph:
114 3b0f3d61 2020-01-22 neels * x = atom index in left-side source, y = atom index in the right-side source.
116 0d27172a 2020-05-06 neels * Only one forward column and one backward column are kept in mem, each need at
117 0d27172a 2020-05-06 neels * most left.len + 1 + right.len items. Note that each d step occupies either
118 0d27172a 2020-05-06 neels * the even or the odd items of a column: if e.g. the previous column is in the
119 0d27172a 2020-05-06 neels * odd items, the next column is formed in the even items, without overwriting
120 0d27172a 2020-05-06 neels * the previous column's results.
122 0d27172a 2020-05-06 neels * Also note that from the diagonal index k and the x coordinate, the y
123 0d27172a 2020-05-06 neels * coordinate can be derived:
124 3b0f3d61 2020-01-22 neels * y = x - k
125 0d27172a 2020-05-06 neels * Hence the state array only needs to keep the x coordinate, i.e. the position
126 0d27172a 2020-05-06 neels * in the left-hand file, and the y coordinate, i.e. position in the right-hand
127 0d27172a 2020-05-06 neels * file, is derived from the index in the state array.
129 0d27172a 2020-05-06 neels * The two traces meet at 4,3, the first step (here found in the forward
130 0d27172a 2020-05-06 neels * traversal) where a forward position is on or past a backward traced position
131 0d27172a 2020-05-06 neels * on the same diagonal.
133 3b0f3d61 2020-01-22 neels * This divides the problem space into:
135 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
136 3b0f3d61 2020-01-22 neels * A B C D E
137 3b0f3d61 2020-01-22 neels * 0 o-o-o-o-o
138 3b0f3d61 2020-01-22 neels * X | | | | |
139 3b0f3d61 2020-01-22 neels * 1 o-o-o-o-o
140 3b0f3d61 2020-01-22 neels * B | |\| | |
141 3b0f3d61 2020-01-22 neels * 2 o-o-o-o-o
142 3b0f3d61 2020-01-22 neels * C | | |\| |
143 3b0f3d61 2020-01-22 neels * 3 o-o-o-o-*-o *: forward and backward meet here
147 3b0f3d61 2020-01-22 neels * Doing the same on each section lead to:
149 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
150 3b0f3d61 2020-01-22 neels * A B C D E
153 3b0f3d61 2020-01-22 neels * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
154 3b0f3d61 2020-01-22 neels * B \ f: then forward d=2 reaches here (sliding down the snake)
155 3b0f3d61 2020-01-22 neels * 2 o As result, the box from b to f is found to be identical;
156 0d27172a 2020-05-06 neels * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial
157 0d27172a 2020-05-06 neels * 3 f-o tail 3,3 to 4,3.
161 3b0f3d61 2020-01-22 neels * 4 o *: forward and backward meet here
163 3b0f3d61 2020-01-22 neels * and solving the last top left box gives:
165 3b0f3d61 2020-01-22 neels * 0 1 2 3 4 5
166 3b0f3d61 2020-01-22 neels * A B C D E -A
167 3b0f3d61 2020-01-22 neels * 0 o-o +X
179 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))
180 3b0f3d61 2020-01-22 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
181 3b0f3d61 2020-01-22 neels #define k_to_c(K, DELTA) ((K) + (DELTA))
182 3b0f3d61 2020-01-22 neels #define c_to_k(C, DELTA) ((C) - (DELTA))
184 3b0f3d61 2020-01-22 neels /* Do one forwards step in the "divide and conquer" graph traversal.
185 3b0f3d61 2020-01-22 neels * left: the left side to diff.
186 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
187 0d27172a 2020-05-06 neels * kd_forward: the traversal state for forwards traversal, modified by this
188 0d27172a 2020-05-06 neels * function.
189 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
190 0d27172a 2020-05-06 neels * kd_forward points at the center of the state array, allowing
191 0d27172a 2020-05-06 neels * negative indexes.
192 0d27172a 2020-05-06 neels * kd_backward: the traversal state for backwards traversal, to find a meeting
194 0d27172a 2020-05-06 neels * Since forwards is done first, kd_backward will be valid for d -
195 0d27172a 2020-05-06 neels * 1, not d.
196 0d27172a 2020-05-06 neels * kd_backward points at the center of the state array, allowing
197 0d27172a 2020-05-06 neels * negative indexes.
198 0d27172a 2020-05-06 neels * d: Step or distance counter, indicating for what value of d the kd_forward
199 0d27172a 2020-05-06 neels * should be populated.
200 0d27172a 2020-05-06 neels * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
201 0d27172a 2020-05-06 neels * be for d == 0.
202 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
203 0d27172a 2020-05-06 neels * Return true when a meeting point has been identified.
205 61a7b578 2020-05-06 neels static bool
206 61a7b578 2020-05-06 neels diff_divide_myers_forward(struct diff_data *left, struct diff_data *right,
207 61a7b578 2020-05-06 neels int *kd_forward, int *kd_backward, int d,
208 61a7b578 2020-05-06 neels struct diff_box *meeting_snake)
210 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
214 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
216 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
217 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
218 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the Myers
219 0d27172a 2020-05-06 neels * graph, don't calculate it. */
220 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len)
221 0d27172a 2020-05-06 neels debug(" %d k < -(int)right->atoms.len %d\n", k,
222 0d27172a 2020-05-06 neels -(int)right->atoms.len);
224 0d27172a 2020-05-06 neels debug(" %d k > left->atoms.len %d\n", k,
225 0d27172a 2020-05-06 neels left->atoms.len);
226 3b0f3d61 2020-01-22 neels if (k < 0) {
227 0d27172a 2020-05-06 neels /* We are traversing negatively, and already
228 0d27172a 2020-05-06 neels * below the entire graph, nothing will come of
229 0d27172a 2020-05-06 neels * this. */
230 3b0f3d61 2020-01-22 neels debug(" break");
233 3b0f3d61 2020-01-22 neels debug(" continue");
236 3b0f3d61 2020-01-22 neels debug("- k = %d\n", k);
237 3b0f3d61 2020-01-22 neels if (d == 0) {
238 0d27172a 2020-05-06 neels /* This is the initializing step. There is no prev_k
239 0d27172a 2020-05-06 neels * yet, get the initial x from the top left of the Myers
240 0d27172a 2020-05-06 neels * graph. */
243 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring moving rightwards in
244 0d27172a 2020-05-06 neels * the Myers graph.
245 0d27172a 2020-05-06 neels * For this, all k should derive from k - 1, only the bottom
246 0d27172a 2020-05-06 neels * most k derive from k + 1:
248 3b0f3d61 2020-01-22 neels * | d= 0 1 2
249 3b0f3d61 2020-01-22 neels * ----+----------------
251 3b0f3d61 2020-01-22 neels * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
255 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
257 0d27172a 2020-05-06 neels * -1 | 0,1 <-- bottom most for d=1 from
258 0d27172a 2020-05-06 neels * | \\ prev_k = -1 + 1 = 0
259 0d27172a 2020-05-06 neels * -2 | 0,2 <-- bottom most for d=2 from
260 0d27172a 2020-05-06 neels * prev_k = -2 + 1 = -1
262 0d27172a 2020-05-06 neels * Except when a k + 1 from a previous run already means a
263 0d27172a 2020-05-06 neels * further advancement in the graph.
264 3b0f3d61 2020-01-22 neels * If k == d, there is no k + 1 and k - 1 is the only option.
265 0d27172a 2020-05-06 neels * If k < d, use k + 1 in case that yields a larger x. Also use
266 0d27172a 2020-05-06 neels * k + 1 if k - 1 is outside the graph.
268 0d27172a 2020-05-06 neels else if (k > -d
269 0d27172a 2020-05-06 neels && (k == d
270 0d27172a 2020-05-06 neels || (k - 1 >= -(int)right->atoms.len
271 0d27172a 2020-05-06 neels && kd_forward[k - 1] >= kd_forward[k + 1]))) {
272 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
273 0d27172a 2020-05-06 neels * From position prev_k, step to the right in the Myers
274 0d27172a 2020-05-06 neels * graph: x += 1.
276 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
277 f71e8098 2020-05-05 neels int prev_x = kd_forward[prev_k];
278 3b0f3d61 2020-01-22 neels x = prev_x + 1;
280 3b0f3d61 2020-01-22 neels /* The bottom most one.
281 0d27172a 2020-05-06 neels * From position prev_k, step to the bottom in the Myers
282 0d27172a 2020-05-06 neels * graph: y += 1.
283 0d27172a 2020-05-06 neels * Incrementing y is achieved by decrementing k while
284 0d27172a 2020-05-06 neels * keeping the same x.
285 3b0f3d61 2020-01-22 neels * (since we're deriving y from y = x - k).
287 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
288 f71e8098 2020-05-05 neels int prev_x = kd_forward[prev_k];
289 3b0f3d61 2020-01-22 neels x = prev_x;
292 f71e8098 2020-05-05 neels int x_before_slide = x;
293 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
294 3b0f3d61 2020-01-22 neels while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len
295 0d27172a 2020-05-06 neels && diff_atom_same(&left->atoms.head[x],
296 0d27172a 2020-05-06 neels &right->atoms.head[xk_to_y(x, k)]))
298 3b0f3d61 2020-01-22 neels kd_forward[k] = x;
299 c5419a05 2020-05-05 neels if (x_before_slide != x) {
300 c5419a05 2020-05-05 neels debug(" down %d similar lines\n", x - x_before_slide);
303 3b0f3d61 2020-01-22 neels if (DEBUG) {
305 3b0f3d61 2020-01-22 neels for (fi = d; fi >= k; fi--) {
306 0d27172a 2020-05-06 neels debug("kd_forward[%d] = (%d, %d)\n", fi,
307 0d27172a 2020-05-06 neels kd_forward[fi], kd_forward[fi] - fi);
311 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
312 3b0f3d61 2020-01-22 neels || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
315 0d27172a 2020-05-06 neels /* Figured out a new forwards traversal, see if this has gone
316 0d27172a 2020-05-06 neels * onto or even past a preceding backwards traversal.
318 0d27172a 2020-05-06 neels * If the delta in length is odd, then d and backwards_d hit the
319 0d27172a 2020-05-06 neels * same state indexes:
320 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
321 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
327 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,3 1
329 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,4<-- 0
331 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,4 -1
333 3b0f3d61 2020-01-22 neels * -1 | 0,1 -2
335 3b0f3d61 2020-01-22 neels * -2 | 0,2 -3
338 0d27172a 2020-05-06 neels * If the delta is even, they end up off-by-one, i.e. on
339 0d27172a 2020-05-06 neels * different diagonals:
341 3b0f3d61 2020-01-22 neels * | d= 0 1 2 1 0
342 3b0f3d61 2020-01-22 neels * ----+---------------- ----------------
346 3b0f3d61 2020-01-22 neels * 2 | 2,0 off 2
348 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3 1
349 3b0f3d61 2020-01-22 neels * | / // \
350 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4<-- 0
352 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4 -1
354 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
357 0d27172a 2020-05-06 neels * So in the forward path, we can only match up diagonals when
358 0d27172a 2020-05-06 neels * the delta is odd.
360 fd42ca98 2020-05-05 neels if ((delta & 1) == 0)
362 0d27172a 2020-05-06 neels /* Forwards is done first, so the backwards one was still at
363 0d27172a 2020-05-06 neels * d - 1. Can't do this for d == 0. */
364 3b0f3d61 2020-01-22 neels int backwards_d = d - 1;
365 fd42ca98 2020-05-05 neels if (backwards_d < 0)
368 fd42ca98 2020-05-05 neels debug("backwards_d = %d\n", backwards_d);
370 0d27172a 2020-05-06 neels /* If both sides have the same length, forward and backward
371 0d27172a 2020-05-06 neels * start on the same diagonal, meaning the backwards state index
373 0d27172a 2020-05-06 neels * As soon as the lengths are not the same, the backwards
374 0d27172a 2020-05-06 neels * traversal starts on a different diagonal, and c = k shifted
375 0d27172a 2020-05-06 neels * by the difference in length.
377 fd42ca98 2020-05-05 neels int c = k_to_c(k, delta);
379 0d27172a 2020-05-06 neels /* When the file sizes are very different, the traversal trees
380 0d27172a 2020-05-06 neels * start on far distant diagonals.
381 0d27172a 2020-05-06 neels * They don't necessarily meet straight on. See whether this
382 0d27172a 2020-05-06 neels * forward value is on a diagonal that is also valid in
383 0d27172a 2020-05-06 neels * kd_backward[], and match them if so. */
384 fd42ca98 2020-05-05 neels if (c >= -backwards_d && c <= backwards_d) {
385 0d27172a 2020-05-06 neels /* Current k is on a diagonal that exists in
386 0d27172a 2020-05-06 neels * kd_backward[]. If the two x positions have met or
387 0d27172a 2020-05-06 neels * passed (forward walked onto or past backward), then
388 0d27172a 2020-05-06 neels * we've found a midpoint / a mid-box.
390 0d27172a 2020-05-06 neels * When forwards and backwards traversals meet, the
391 0d27172a 2020-05-06 neels * endpoints of the mid-snake are not the two points in
392 0d27172a 2020-05-06 neels * kd_forward and kd_backward, but rather the section
393 0d27172a 2020-05-06 neels * that was slid (if any) of the current
394 0d27172a 2020-05-06 neels * forward/backward traversal only.
396 f71e8098 2020-05-05 neels * For example:
418 0d27172a 2020-05-06 neels * The forward traversal reached M from the top and slid
419 0d27172a 2020-05-06 neels * downwards to A. The backward traversal already
420 0d27172a 2020-05-06 neels * reached X, which is not a straight line from M
421 0d27172a 2020-05-06 neels * anymore, so picking a mid-snake from M to X would
422 0d27172a 2020-05-06 neels * yield a mistake.
424 0d27172a 2020-05-06 neels * The correct mid-snake is between M and A. M is where
425 0d27172a 2020-05-06 neels * the forward traversal hit the diagonal that the
426 0d27172a 2020-05-06 neels * backward traversal has already passed, and A is what
427 0d27172a 2020-05-06 neels * it reaches when sliding down identical lines.
429 fd42ca98 2020-05-05 neels int backward_x = kd_backward[c];
430 50198b5f 2020-05-05 neels debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
431 0d27172a 2020-05-06 neels k, c, x, xk_to_y(x, k), backward_x,
432 0d27172a 2020-05-06 neels xc_to_y(backward_x, c, delta));
433 f71e8098 2020-05-05 neels if (x >= backward_x) {
434 fd42ca98 2020-05-05 neels *meeting_snake = (struct diff_box){
435 f71e8098 2020-05-05 neels .left_start = x_before_slide,
436 fd42ca98 2020-05-05 neels .left_end = x,
437 0d27172a 2020-05-06 neels .right_start = xc_to_y(x_before_slide,
438 0d27172a 2020-05-06 neels c, delta),
439 fd42ca98 2020-05-05 neels .right_end = xk_to_y(x, k),
441 fd42ca98 2020-05-05 neels debug("HIT x=(%u,%u) - y=(%u,%u)\n",
442 fd42ca98 2020-05-05 neels meeting_snake->left_start,
443 fd42ca98 2020-05-05 neels meeting_snake->right_start,
444 fd42ca98 2020-05-05 neels meeting_snake->left_end,
445 fd42ca98 2020-05-05 neels meeting_snake->right_end);
446 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL,
447 0d27172a 2020-05-06 neels kd_forward, d,
448 0d27172a 2020-05-06 neels kd_backward, d-1);
449 a45330b1 2020-05-05 neels return true;
454 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d,
455 0d27172a 2020-05-06 neels kd_backward, d-1);
456 a45330b1 2020-05-05 neels return false;
459 3b0f3d61 2020-01-22 neels /* Do one backwards step in the "divide and conquer" graph traversal.
460 3b0f3d61 2020-01-22 neels * left: the left side to diff.
461 3b0f3d61 2020-01-22 neels * right: the right side to diff against.
462 0d27172a 2020-05-06 neels * kd_forward: the traversal state for forwards traversal, to find a meeting
464 0d27172a 2020-05-06 neels * Since forwards is done first, after this, both kd_forward and
465 0d27172a 2020-05-06 neels * kd_backward will be valid for d.
466 0d27172a 2020-05-06 neels * kd_forward points at the center of the state array, allowing
467 0d27172a 2020-05-06 neels * negative indexes.
468 0d27172a 2020-05-06 neels * kd_backward: the traversal state for backwards traversal, to find a meeting
470 3b0f3d61 2020-01-22 neels * This is carried over between invocations with increasing d.
471 0d27172a 2020-05-06 neels * kd_backward points at the center of the state array, allowing
472 0d27172a 2020-05-06 neels * negative indexes.
473 0d27172a 2020-05-06 neels * d: Step or distance counter, indicating for what value of d the kd_backward
474 0d27172a 2020-05-06 neels * should be populated.
475 0d27172a 2020-05-06 neels * Before the first invocation, kd_backward[0] shall point at the bottom
476 0d27172a 2020-05-06 neels * right of the Myers graph (left.len, right.len).
477 3b0f3d61 2020-01-22 neels * The first invocation will be for d == 1.
478 3b0f3d61 2020-01-22 neels * meeting_snake: resulting meeting point, if any.
479 0d27172a 2020-05-06 neels * Return true when a meeting point has been identified.
481 61a7b578 2020-05-06 neels static bool
482 61a7b578 2020-05-06 neels diff_divide_myers_backward(struct diff_data *left, struct diff_data *right,
483 61a7b578 2020-05-06 neels int *kd_forward, int *kd_backward, int d,
484 61a7b578 2020-05-06 neels struct diff_box *meeting_snake)
486 3b0f3d61 2020-01-22 neels int delta = (int)right->atoms.len - (int)left->atoms.len;
490 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
492 3b0f3d61 2020-01-22 neels for (c = d; c >= -d; c -= 2) {
493 3b0f3d61 2020-01-22 neels if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
494 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the Myers
495 0d27172a 2020-05-06 neels * graph, don't calculate it. */
496 3b0f3d61 2020-01-22 neels if (c < -(int)left->atoms.len)
497 0d27172a 2020-05-06 neels debug(" %d c < -(int)left->atoms.len %d\n", c,
498 0d27172a 2020-05-06 neels -(int)left->atoms.len);
500 0d27172a 2020-05-06 neels debug(" %d c > right->atoms.len %d\n", c,
501 0d27172a 2020-05-06 neels right->atoms.len);
502 3b0f3d61 2020-01-22 neels if (c < 0) {
503 0d27172a 2020-05-06 neels /* We are traversing negatively, and already
504 0d27172a 2020-05-06 neels * below the entire graph, nothing will come of
505 0d27172a 2020-05-06 neels * this. */
506 3b0f3d61 2020-01-22 neels debug(" break");
509 3b0f3d61 2020-01-22 neels debug(" continue");
512 3b0f3d61 2020-01-22 neels debug("- c = %d\n", c);
513 3b0f3d61 2020-01-22 neels if (d == 0) {
514 0d27172a 2020-05-06 neels /* This is the initializing step. There is no prev_c
515 0d27172a 2020-05-06 neels * yet, get the initial x from the bottom right of the
516 0d27172a 2020-05-06 neels * Myers graph. */
517 3b0f3d61 2020-01-22 neels x = left->atoms.len;
519 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring moving rightwards in
520 0d27172a 2020-05-06 neels * the Myers graph.
521 0d27172a 2020-05-06 neels * For this, all c should derive from c - 1, only the bottom
522 0d27172a 2020-05-06 neels * most c derive from c + 1:
525 3b0f3d61 2020-01-22 neels * ---------------------------------------------------
529 3b0f3d61 2020-01-22 neels * from prev_c = c - 1 --> 5,2 2
533 3b0f3d61 2020-01-22 neels * 4,3 5,4<-- 0
535 3b0f3d61 2020-01-22 neels * bottom most for d=1 from c + 1 --> 4,4 -1
537 3b0f3d61 2020-01-22 neels * bottom most for d=2 --> 3,4 -2
539 0d27172a 2020-05-06 neels * Except when a c + 1 from a previous run already means a
540 0d27172a 2020-05-06 neels * further advancement in the graph.
541 3b0f3d61 2020-01-22 neels * If c == d, there is no c + 1 and c - 1 is the only option.
542 0d27172a 2020-05-06 neels * If c < d, use c + 1 in case that yields a larger x.
543 0d27172a 2020-05-06 neels * Also use c + 1 if c - 1 is outside the graph.
545 3b0f3d61 2020-01-22 neels else if (c > -d && (c == d
546 3b0f3d61 2020-01-22 neels || (c - 1 >= -(int)right->atoms.len
547 3b0f3d61 2020-01-22 neels && kd_backward[c - 1] <= kd_backward[c + 1]))) {
548 3b0f3d61 2020-01-22 neels /* A top one.
549 0d27172a 2020-05-06 neels * From position prev_c, step upwards in the Myers
550 0d27172a 2020-05-06 neels * graph: y -= 1.
551 0d27172a 2020-05-06 neels * Decrementing y is achieved by incrementing c while
552 0d27172a 2020-05-06 neels * keeping the same x. (since we're deriving y from
553 0d27172a 2020-05-06 neels * y = x - c + delta).
555 3b0f3d61 2020-01-22 neels int prev_c = c - 1;
556 f71e8098 2020-05-05 neels int prev_x = kd_backward[prev_c];
557 3b0f3d61 2020-01-22 neels x = prev_x;
559 3b0f3d61 2020-01-22 neels /* The bottom most one.
560 0d27172a 2020-05-06 neels * From position prev_c, step to the left in the Myers
561 0d27172a 2020-05-06 neels * graph: x -= 1.
563 3b0f3d61 2020-01-22 neels int prev_c = c + 1;
564 f71e8098 2020-05-05 neels int prev_x = kd_backward[prev_c];
565 3b0f3d61 2020-01-22 neels x = prev_x - 1;
568 0d27172a 2020-05-06 neels /* Slide up any snake that we might find here (sections of
569 0d27172a 2020-05-06 neels * identical lines on both sides). */
570 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,
572 0d27172a 2020-05-06 neels xc_to_y(x, c, delta)-1);
573 3b0f3d61 2020-01-22 neels if (x > 0) {
574 0d27172a 2020-05-06 neels debug(" l=");
575 0d27172a 2020-05-06 neels debug_dump_atom(left, right, &left->atoms.head[x-1]);
577 3b0f3d61 2020-01-22 neels if (xc_to_y(x, c, delta) > 0) {
578 0d27172a 2020-05-06 neels debug(" r=");
579 0d27172a 2020-05-06 neels debug_dump_atom(right, left,
580 0d27172a 2020-05-06 neels &right->atoms.head[xc_to_y(x, c, delta)-1]);
582 f71e8098 2020-05-05 neels int x_before_slide = x;
583 3b0f3d61 2020-01-22 neels while (x > 0 && xc_to_y(x, c, delta) > 0
584 0d27172a 2020-05-06 neels && diff_atom_same(&left->atoms.head[x-1],
585 0d27172a 2020-05-06 neels &right->atoms.head[xc_to_y(x, c,
586 0d27172a 2020-05-06 neels delta)-1]))
588 3b0f3d61 2020-01-22 neels kd_backward[c] = x;
589 c5419a05 2020-05-05 neels if (x_before_slide != x) {
590 c5419a05 2020-05-05 neels debug(" up %d similar lines\n", x_before_slide - x);
593 3b0f3d61 2020-01-22 neels if (DEBUG) {
595 3b0f3d61 2020-01-22 neels for (fi = d; fi >= c; fi--) {
596 0d27172a 2020-05-06 neels debug("kd_backward[%d] = (%d, %d)\n",
598 0d27172a 2020-05-06 neels kd_backward[fi],
599 3b0f3d61 2020-01-22 neels kd_backward[fi] - fi + delta);
603 3b0f3d61 2020-01-22 neels if (x < 0 || x > left->atoms.len
604 0d27172a 2020-05-06 neels || xc_to_y(x, c, delta) < 0
605 0d27172a 2020-05-06 neels || xc_to_y(x, c, delta) > right->atoms.len)
608 0d27172a 2020-05-06 neels /* Figured out a new backwards traversal, see if this has gone
609 0d27172a 2020-05-06 neels * onto or even past a preceding forwards traversal.
611 0d27172a 2020-05-06 neels * If the delta in length is even, then d and backwards_d hit
612 0d27172a 2020-05-06 neels * the same state indexes -- note how this is different from in
613 0d27172a 2020-05-06 neels * the forwards traversal, because now both d are the same:
615 3b0f3d61 2020-01-22 neels * | d= 0 1 2 2 1 0
616 3b0f3d61 2020-01-22 neels * ----+---------------- --------------------
622 3b0f3d61 2020-01-22 neels * 2 | 2,0====5,2 2
624 3b0f3d61 2020-01-22 neels * 1 | 1,0 5,3 1
626 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3====4,3 5,4<-- 0
628 3b0f3d61 2020-01-22 neels * -1 | 0,1 4,4 -1
630 3b0f3d61 2020-01-22 neels * -2 | 0,2 -2
633 0d27172a 2020-05-06 neels * If the delta is odd, they end up off-by-one, i.e. on
634 0d27172a 2020-05-06 neels * different diagonals.
635 0d27172a 2020-05-06 neels * So in the backward path, we can only match up diagonals when
636 0d27172a 2020-05-06 neels * the delta is even.
638 0d27172a 2020-05-06 neels if ((delta & 1) != 0)
640 0d27172a 2020-05-06 neels /* Forwards was done first, now both d are the same. */
641 0d27172a 2020-05-06 neels int forwards_d = d;
643 0d27172a 2020-05-06 neels /* As soon as the lengths are not the same, the
644 0d27172a 2020-05-06 neels * backwards traversal starts on a different diagonal,
645 0d27172a 2020-05-06 neels * and c = k shifted by the difference in length.
647 0d27172a 2020-05-06 neels int k = c_to_k(c, delta);
649 0d27172a 2020-05-06 neels /* When the file sizes are very different, the traversal trees
650 0d27172a 2020-05-06 neels * start on far distant diagonals.
651 0d27172a 2020-05-06 neels * They don't necessarily meet straight on. See whether this
652 0d27172a 2020-05-06 neels * backward value is also on a valid diagonal in kd_forward[],
653 0d27172a 2020-05-06 neels * and match them if so. */
654 0d27172a 2020-05-06 neels if (k >= -forwards_d && k <= forwards_d) {
655 0d27172a 2020-05-06 neels /* Current c is on a diagonal that exists in
656 0d27172a 2020-05-06 neels * kd_forward[]. If the two x positions have met or
657 0d27172a 2020-05-06 neels * passed (backward walked onto or past forward), then
658 0d27172a 2020-05-06 neels * we've found a midpoint / a mid-box.
660 0d27172a 2020-05-06 neels * When forwards and backwards traversals meet, the
661 0d27172a 2020-05-06 neels * endpoints of the mid-snake are not the two points in
662 0d27172a 2020-05-06 neels * kd_forward and kd_backward, but rather the section
663 0d27172a 2020-05-06 neels * that was slid (if any) of the current
664 0d27172a 2020-05-06 neels * forward/backward traversal only.
666 0d27172a 2020-05-06 neels * For example:
686 0d27172a 2020-05-06 neels * The backward traversal reached M from the bottom and
687 0d27172a 2020-05-06 neels * slid upwards. The forward traversal already reached
688 0d27172a 2020-05-06 neels * X, which is not a straight line from M anymore, so
689 0d27172a 2020-05-06 neels * picking a mid-snake from M to X would yield a
690 0d27172a 2020-05-06 neels * mistake.
692 0d27172a 2020-05-06 neels * The correct mid-snake is between M and A. M is where
693 0d27172a 2020-05-06 neels * the backward traversal hit the diagonal that the
694 0d27172a 2020-05-06 neels * forwards traversal has already passed, and A is what
695 0d27172a 2020-05-06 neels * it reaches when sliding up identical lines.
698 0d27172a 2020-05-06 neels int forward_x = kd_forward[k];
699 0d27172a 2020-05-06 neels debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
700 0d27172a 2020-05-06 neels k, c, forward_x, xk_to_y(forward_x, k),
701 0d27172a 2020-05-06 neels x, xc_to_y(x, c, delta));
702 0d27172a 2020-05-06 neels if (forward_x >= x) {
703 0d27172a 2020-05-06 neels *meeting_snake = (struct diff_box){
704 0d27172a 2020-05-06 neels .left_start = x,
705 0d27172a 2020-05-06 neels .left_end = x_before_slide,
706 0d27172a 2020-05-06 neels .right_start = xc_to_y(x, c, delta),
707 0d27172a 2020-05-06 neels .right_end = xk_to_y(x_before_slide, k),
709 0d27172a 2020-05-06 neels debug("HIT x=%u,%u - y=%u,%u\n",
710 0d27172a 2020-05-06 neels meeting_snake->left_start,
711 0d27172a 2020-05-06 neels meeting_snake->right_start,
712 0d27172a 2020-05-06 neels meeting_snake->left_end,
713 0d27172a 2020-05-06 neels meeting_snake->right_end);
714 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL,
715 0d27172a 2020-05-06 neels kd_forward, d,
716 0d27172a 2020-05-06 neels kd_backward, d);
717 0d27172a 2020-05-06 neels return true;
721 0d27172a 2020-05-06 neels debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward,
723 a45330b1 2020-05-05 neels return false;
726 0d27172a 2020-05-06 neels /* Myers "Divide et Impera": tracing forwards from the start and backwards from
727 0d27172a 2020-05-06 neels * the end to find a midpoint that divides the problem into smaller chunks.
728 0d27172a 2020-05-06 neels * Requires only linear amounts of memory. */
729 61a7b578 2020-05-06 neels enum diff_rc
730 0d27172a 2020-05-06 neels diff_algo_myers_divide(const struct diff_algo_config *algo_config,
731 0d27172a 2020-05-06 neels struct diff_state *state)
733 3b0f3d61 2020-01-22 neels enum diff_rc rc = DIFF_RC_ENOMEM;
734 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
735 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
737 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
738 3b0f3d61 2020-01-22 neels debug("left:\n");
739 3b0f3d61 2020-01-22 neels debug_dump(left);
740 3b0f3d61 2020-01-22 neels debug("right:\n");
741 3b0f3d61 2020-01-22 neels debug_dump(right);
742 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
744 0d27172a 2020-05-06 neels /* Allocate two columns of a Myers graph, one for the forward and one
745 0d27172a 2020-05-06 neels * for the backward traversal. */
746 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
747 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1;
748 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len << 1;
749 3b0f3d61 2020-01-22 neels int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
750 3b0f3d61 2020-01-22 neels if (!kd_buf)
751 3b0f3d61 2020-01-22 neels return DIFF_RC_ENOMEM;
753 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
754 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
755 3b0f3d61 2020-01-22 neels int *kd_forward = kd_buf;
756 3b0f3d61 2020-01-22 neels int *kd_backward = kd_buf + kd_len;
758 0d27172a 2020-05-06 neels /* The 'k' axis in Myers spans positive and negative indexes, so point
759 0d27172a 2020-05-06 neels * the kd to the middle.
760 3b0f3d61 2020-01-22 neels * It is then possible to index from -max/2 .. max/2. */
761 3b0f3d61 2020-01-22 neels kd_forward += max/2;
762 3b0f3d61 2020-01-22 neels kd_backward += max/2;
765 3b0f3d61 2020-01-22 neels struct diff_box mid_snake = {};
766 a45330b1 2020-05-05 neels bool found_midpoint = false;
767 3b0f3d61 2020-01-22 neels for (d = 0; d <= (max/2); d++) {
768 3b0f3d61 2020-01-22 neels debug("-- d=%d\n", d);
769 a45330b1 2020-05-05 neels found_midpoint = diff_divide_myers_forward(left, right, kd_forward, kd_backward, d, &mid_snake);
770 a45330b1 2020-05-05 neels if (found_midpoint)
772 a45330b1 2020-05-05 neels found_midpoint = diff_divide_myers_backward(left, right, kd_forward, kd_backward, d, &mid_snake);
773 a45330b1 2020-05-05 neels if (found_midpoint)
777 a45330b1 2020-05-05 neels if (!found_midpoint) {
778 0d27172a 2020-05-06 neels /* Divide and conquer failed to find a meeting point. Use the
779 0d27172a 2020-05-06 neels * fallback_algo defined in the algo_config (leave this to the
780 0d27172a 2020-05-06 neels * caller). This is just paranoia/sanity, we normally should
781 0d27172a 2020-05-06 neels * always find a midpoint.
783 3b0f3d61 2020-01-22 neels debug(" no midpoint \n");
784 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
785 3b0f3d61 2020-01-22 neels goto return_rc;
787 3b0f3d61 2020-01-22 neels debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
788 3b0f3d61 2020-01-22 neels mid_snake.left_start, mid_snake.left_end, left->atoms.len,
789 0d27172a 2020-05-06 neels mid_snake.right_start, mid_snake.right_end,
790 0d27172a 2020-05-06 neels right->atoms.len);
792 3b0f3d61 2020-01-22 neels /* Section before the mid-snake. */
793 3b0f3d61 2020-01-22 neels debug("Section before the mid-snake\n");
795 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[0];
796 3b0f3d61 2020-01-22 neels unsigned int left_section_len = mid_snake.left_start;
797 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[0];
798 3b0f3d61 2020-01-22 neels unsigned int right_section_len = mid_snake.right_start;
800 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
801 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
802 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
803 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
804 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
805 0d27172a 2020-05-06 neels right_atom,
806 0d27172a 2020-05-06 neels right_section_len))
807 3b0f3d61 2020-01-22 neels goto return_rc;
808 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
809 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
810 0d27172a 2020-05-06 neels * "minus" chunk, then. */
811 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
812 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
813 3b0f3d61 2020-01-22 neels right_atom, 0))
814 3b0f3d61 2020-01-22 neels goto return_rc;
815 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
816 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
817 0d27172a 2020-05-06 neels * "plus" chunk, then. */
818 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
819 3b0f3d61 2020-01-22 neels left_atom, 0,
820 0d27172a 2020-05-06 neels right_atom,
821 0d27172a 2020-05-06 neels right_section_len))
822 3b0f3d61 2020-01-22 neels goto return_rc;
824 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
825 0d27172a 2020-05-06 neels * nothing before the mid-snake. */
827 a45330b1 2020-05-05 neels if (!diff_box_empty(&mid_snake)) {
828 0d27172a 2020-05-06 neels /* The midpoint is a "snake", i.e. on a section of
829 0d27172a 2020-05-06 neels * identical data on both sides: that section
830 0d27172a 2020-05-06 neels * immediately becomes a solved diff chunk. */
831 a45330b1 2020-05-05 neels debug("the mid-snake\n");
832 a45330b1 2020-05-05 neels if (!diff_state_add_chunk(state, true,
833 0d27172a 2020-05-06 neels &left->atoms.head[mid_snake.left_start],
834 0d27172a 2020-05-06 neels mid_snake.left_end - mid_snake.left_start,
835 0d27172a 2020-05-06 neels &right->atoms.head[mid_snake.right_start],
836 0d27172a 2020-05-06 neels mid_snake.right_end - mid_snake.right_start))
837 a45330b1 2020-05-05 neels goto return_rc;
840 3b0f3d61 2020-01-22 neels /* Section after the mid-snake. */
841 3b0f3d61 2020-01-22 neels debug("Section after the mid-snake\n");
842 0d27172a 2020-05-06 neels debug(" left_end %u right_end %u\n",
843 0d27172a 2020-05-06 neels mid_snake.left_end, mid_snake.right_end);
844 0d27172a 2020-05-06 neels debug(" left_count %u right_count %u\n",
845 0d27172a 2020-05-06 neels left->atoms.len, right->atoms.len);
846 3b0f3d61 2020-01-22 neels left_atom = &left->atoms.head[mid_snake.left_end];
847 3b0f3d61 2020-01-22 neels left_section_len = left->atoms.len - mid_snake.left_end;
848 3b0f3d61 2020-01-22 neels right_atom = &right->atoms.head[mid_snake.right_end];
849 3b0f3d61 2020-01-22 neels right_section_len = right->atoms.len - mid_snake.right_end;
851 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
852 0d27172a 2020-05-06 neels /* Record an unsolved chunk, the caller will apply
853 0d27172a 2020-05-06 neels * inner_algo() on this chunk. */
854 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, false,
855 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
856 0d27172a 2020-05-06 neels right_atom,
857 0d27172a 2020-05-06 neels right_section_len))
858 3b0f3d61 2020-01-22 neels goto return_rc;
859 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
860 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
861 0d27172a 2020-05-06 neels * "minus" chunk, then. */
862 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
863 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
864 3b0f3d61 2020-01-22 neels right_atom, 0))
865 3b0f3d61 2020-01-22 neels goto return_rc;
866 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
867 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
868 0d27172a 2020-05-06 neels * "plus" chunk, then. */
869 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
870 3b0f3d61 2020-01-22 neels left_atom, 0,
871 0d27172a 2020-05-06 neels right_atom,
872 0d27172a 2020-05-06 neels right_section_len))
873 3b0f3d61 2020-01-22 neels goto return_rc;
875 0d27172a 2020-05-06 neels /* else: left_section_len == 0 and right_section_len == 0, i.e.
876 0d27172a 2020-05-06 neels * nothing after the mid-snake. */
879 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
881 3b0f3d61 2020-01-22 neels return_rc:
882 3b0f3d61 2020-01-22 neels free(kd_buf);
883 3b0f3d61 2020-01-22 neels debug("** END %s\n", __func__);
884 3b0f3d61 2020-01-22 neels return rc;
887 0d27172a 2020-05-06 neels /* Myers Diff tracing from the start all the way through to the end, requiring
888 0d27172a 2020-05-06 neels * quadratic amounts of memory. This can fail if the required space surpasses
889 0d27172a 2020-05-06 neels * algo_config->permitted_state_size. */
890 61a7b578 2020-05-06 neels enum diff_rc
891 0d27172a 2020-05-06 neels diff_algo_myers(const struct diff_algo_config *algo_config,
892 0d27172a 2020-05-06 neels struct diff_state *state)
894 0d27172a 2020-05-06 neels /* do a diff_divide_myers_forward() without a _backward(), so that it
895 0d27172a 2020-05-06 neels * walks forward across the entire files to reach the end. Keep each
896 0d27172a 2020-05-06 neels * run's state, and do a final backtrace. */
897 3b0f3d61 2020-01-22 neels enum diff_rc rc = DIFF_RC_ENOMEM;
898 3b0f3d61 2020-01-22 neels struct diff_data *left = &state->left;
899 3b0f3d61 2020-01-22 neels struct diff_data *right = &state->right;
901 3b0f3d61 2020-01-22 neels debug("\n** %s\n", __func__);
902 3b0f3d61 2020-01-22 neels debug("left:\n");
903 3b0f3d61 2020-01-22 neels debug_dump(left);
904 3b0f3d61 2020-01-22 neels debug("right:\n");
905 3b0f3d61 2020-01-22 neels debug_dump(right);
906 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
908 0d27172a 2020-05-06 neels /* Allocate two columns of a Myers graph, one for the forward and one
909 0d27172a 2020-05-06 neels * for the backward traversal. */
910 3b0f3d61 2020-01-22 neels unsigned int max = left->atoms.len + right->atoms.len;
911 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1 + max;
912 3b0f3d61 2020-01-22 neels size_t kd_buf_size = kd_len * kd_len;
913 50198b5f 2020-05-05 neels size_t kd_state_size = kd_buf_size * sizeof(int);
914 3b0f3d61 2020-01-22 neels debug("state size: %zu\n", kd_buf_size);
915 3b0f3d61 2020-01-22 neels if (kd_buf_size < kd_len /* overflow? */
916 50198b5f 2020-05-05 neels || kd_state_size > algo_config->permitted_state_size) {
917 3b0f3d61 2020-01-22 neels debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
918 50198b5f 2020-05-05 neels kd_state_size, algo_config->permitted_state_size);
919 3b0f3d61 2020-01-22 neels return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
922 3b0f3d61 2020-01-22 neels int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
923 3b0f3d61 2020-01-22 neels if (!kd_buf)
924 3b0f3d61 2020-01-22 neels return DIFF_RC_ENOMEM;
926 3b0f3d61 2020-01-22 neels for (i = 0; i < kd_buf_size; i++)
927 3b0f3d61 2020-01-22 neels kd_buf[i] = -1;
929 0d27172a 2020-05-06 neels /* The 'k' axis in Myers spans positive and negative indexes, so point
930 0d27172a 2020-05-06 neels * the kd to the middle.
931 3b0f3d61 2020-01-22 neels * It is then possible to index from -max .. max. */
932 3b0f3d61 2020-01-22 neels int *kd_origin = kd_buf + max;
933 3b0f3d61 2020-01-22 neels int *kd_column = kd_origin;
936 3b0f3d61 2020-01-22 neels int backtrack_d = -1;
937 3b0f3d61 2020-01-22 neels int backtrack_k = 0;
940 3b0f3d61 2020-01-22 neels for (d = 0; d <= max; d++, kd_column += kd_len) {
941 3b0f3d61 2020-01-22 neels debug("-- d=%d\n", d);
943 3b0f3d61 2020-01-22 neels debug("-- %s d=%d\n", __func__, d);
945 3b0f3d61 2020-01-22 neels for (k = d; k >= -d; k -= 2) {
946 0d27172a 2020-05-06 neels if (k < -(int)right->atoms.len
947 0d27172a 2020-05-06 neels || k > (int)left->atoms.len) {
948 0d27172a 2020-05-06 neels /* This diagonal is completely outside of the
949 0d27172a 2020-05-06 neels * Myers graph, don't calculate it. */
950 3b0f3d61 2020-01-22 neels if (k < -(int)right->atoms.len)
951 0d27172a 2020-05-06 neels debug(" %d k <"
952 0d27172a 2020-05-06 neels " -(int)right->atoms.len %d\n",
953 0d27172a 2020-05-06 neels k, -(int)right->atoms.len);
955 0d27172a 2020-05-06 neels debug(" %d k > left->atoms.len %d\n", k,
956 0d27172a 2020-05-06 neels left->atoms.len);
957 3b0f3d61 2020-01-22 neels if (k < 0) {
958 0d27172a 2020-05-06 neels /* We are traversing negatively, and
959 0d27172a 2020-05-06 neels * already below the entire graph,
960 0d27172a 2020-05-06 neels * nothing will come of this. */
961 3b0f3d61 2020-01-22 neels debug(" break");
964 3b0f3d61 2020-01-22 neels debug(" continue");
968 3b0f3d61 2020-01-22 neels debug("- k = %d\n", k);
969 3b0f3d61 2020-01-22 neels if (d == 0) {
970 0d27172a 2020-05-06 neels /* This is the initializing step. There is no
971 0d27172a 2020-05-06 neels * prev_k yet, get the initial x from the top
972 0d27172a 2020-05-06 neels * left of the Myers graph. */
975 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
977 0d27172a 2020-05-06 neels /* Favoring "-" lines first means favoring
978 0d27172a 2020-05-06 neels * moving rightwards in the Myers graph.
979 0d27172a 2020-05-06 neels * For this, all k should derive from k - 1,
980 0d27172a 2020-05-06 neels * only the bottom most k derive from k + 1:
982 3b0f3d61 2020-01-22 neels * | d= 0 1 2
983 3b0f3d61 2020-01-22 neels * ----+----------------
985 0d27172a 2020-05-06 neels * 2 | 2,0 <-- from
986 0d27172a 2020-05-06 neels * | / prev_k = 2 - 1 = 1
989 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3
991 0d27172a 2020-05-06 neels * -1 | 0,1 <-- bottom most for d=1
992 0d27172a 2020-05-06 neels * | \\ from prev_k = -1+1 = 0
993 0d27172a 2020-05-06 neels * -2 | 0,2 <-- bottom most for
994 0d27172a 2020-05-06 neels * d=2 from
995 0d27172a 2020-05-06 neels * prev_k = -2+1 = -1
997 0d27172a 2020-05-06 neels * Except when a k + 1 from a previous run
998 0d27172a 2020-05-06 neels * already means a further advancement in the
1000 0d27172a 2020-05-06 neels * If k == d, there is no k + 1 and k - 1 is the
1001 0d27172a 2020-05-06 neels * only option.
1002 0d27172a 2020-05-06 neels * If k < d, use k + 1 in case that yields a
1003 0d27172a 2020-05-06 neels * larger x. Also use k + 1 if k - 1 is outside
1004 0d27172a 2020-05-06 neels * the graph.
1006 0d27172a 2020-05-06 neels if (k > -d
1007 0d27172a 2020-05-06 neels && (k == d
1008 0d27172a 2020-05-06 neels || (k - 1 >= -(int)right->atoms.len
1009 0d27172a 2020-05-06 neels && kd_prev_column[k - 1]
1010 0d27172a 2020-05-06 neels >= kd_prev_column[k + 1]))) {
1011 3b0f3d61 2020-01-22 neels /* Advance from k - 1.
1012 0d27172a 2020-05-06 neels * From position prev_k, step to the
1013 0d27172a 2020-05-06 neels * right in the Myers graph: x += 1.
1015 3b0f3d61 2020-01-22 neels int prev_k = k - 1;
1016 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
1017 3b0f3d61 2020-01-22 neels x = prev_x + 1;
1019 3b0f3d61 2020-01-22 neels /* The bottom most one.
1020 0d27172a 2020-05-06 neels * From position prev_k, step to the
1021 0d27172a 2020-05-06 neels * bottom in the Myers graph: y += 1.
1022 0d27172a 2020-05-06 neels * Incrementing y is achieved by
1023 0d27172a 2020-05-06 neels * decrementing k while keeping the same
1024 0d27172a 2020-05-06 neels * x. (since we're deriving y from y =
1025 0d27172a 2020-05-06 neels * x - k).
1027 3b0f3d61 2020-01-22 neels int prev_k = k + 1;
1028 3b0f3d61 2020-01-22 neels int prev_x = kd_prev_column[prev_k];
1029 3b0f3d61 2020-01-22 neels x = prev_x;
1033 3b0f3d61 2020-01-22 neels /* Slide down any snake that we might find here. */
1034 0d27172a 2020-05-06 neels while (x < left->atoms.len
1035 0d27172a 2020-05-06 neels && xk_to_y(x, k) < right->atoms.len
1036 0d27172a 2020-05-06 neels && diff_atom_same(&left->atoms.head[x],
1037 0d27172a 2020-05-06 neels &right->atoms.head[xk_to_y(x, k)]))
1039 3b0f3d61 2020-01-22 neels kd_column[k] = x;
1041 3b0f3d61 2020-01-22 neels if (DEBUG) {
1043 3b0f3d61 2020-01-22 neels for (fi = d; fi >= k; fi-=2) {
1044 0d27172a 2020-05-06 neels debug("kd_column[%d] = (%d, %d)\n", fi,
1045 0d27172a 2020-05-06 neels kd_column[fi],
1046 0d27172a 2020-05-06 neels kd_column[fi] - fi);
1050 0d27172a 2020-05-06 neels if (x == left->atoms.len
1051 0d27172a 2020-05-06 neels && xk_to_y(x, k) == right->atoms.len) {
1052 3b0f3d61 2020-01-22 neels /* Found a path */
1053 3b0f3d61 2020-01-22 neels backtrack_d = d;
1054 3b0f3d61 2020-01-22 neels backtrack_k = k;
1055 3b0f3d61 2020-01-22 neels debug("Reached the end at d = %d, k = %d\n",
1056 3b0f3d61 2020-01-22 neels backtrack_d, backtrack_k);
1061 3b0f3d61 2020-01-22 neels if (backtrack_d >= 0)
1065 50198b5f 2020-05-05 neels debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
1067 3b0f3d61 2020-01-22 neels /* backtrack. A matrix spanning from start to end of the file is ready:
1069 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
1070 3b0f3d61 2020-01-22 neels * ----+---------------------------------
1074 3b0f3d61 2020-01-22 neels * 2 | 2,0
1076 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
1077 3b0f3d61 2020-01-22 neels * | / / \
1078 3b0f3d61 2020-01-22 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
1079 3b0f3d61 2020-01-22 neels * | \ / \
1080 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
1082 3b0f3d61 2020-01-22 neels * -2 | 0,2
1085 3b0f3d61 2020-01-22 neels * From (4,4) backwards, find the previous position that is the largest, and remember it.
1088 3b0f3d61 2020-01-22 neels for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
1089 3b0f3d61 2020-01-22 neels x = kd_column[k];
1090 3b0f3d61 2020-01-22 neels y = xk_to_y(x, k);
1092 0d27172a 2020-05-06 neels /* When the best position is identified, remember it for that
1093 0d27172a 2020-05-06 neels * kd_column.
1094 0d27172a 2020-05-06 neels * That kd_column is no longer needed otherwise, so just
1095 0d27172a 2020-05-06 neels * re-purpose kd_column[0] = x and kd_column[1] = y,
1096 3b0f3d61 2020-01-22 neels * so that there is no need to allocate more memory.
1098 3b0f3d61 2020-01-22 neels kd_column[0] = x;
1099 3b0f3d61 2020-01-22 neels kd_column[1] = y;
1100 3b0f3d61 2020-01-22 neels debug("Backtrack d=%d: xy=(%d, %d)\n",
1101 3b0f3d61 2020-01-22 neels d, kd_column[0], kd_column[1]);
1103 3b0f3d61 2020-01-22 neels /* Don't access memory before kd_buf */
1104 3b0f3d61 2020-01-22 neels if (d == 0)
1106 3b0f3d61 2020-01-22 neels int *kd_prev_column = kd_column - kd_len;
1108 3b0f3d61 2020-01-22 neels /* When y == 0, backtracking downwards (k-1) is the only way.
1109 3b0f3d61 2020-01-22 neels * When x == 0, backtracking upwards (k+1) is the only way.
1111 3b0f3d61 2020-01-22 neels * | d= 0 1 2 3 4
1112 3b0f3d61 2020-01-22 neels * ----+---------------------------------
1115 3b0f3d61 2020-01-22 neels * | ..y == 0
1116 3b0f3d61 2020-01-22 neels * 2 | 2,0
1118 3b0f3d61 2020-01-22 neels * 1 | 1,0 4,3
1119 3b0f3d61 2020-01-22 neels * | / / \
1120 0d27172a 2020-05-06 neels * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4,
1121 0d27172a 2020-05-06 neels * | \ / \ backtrack_k = 0
1122 3b0f3d61 2020-01-22 neels * -1 | 0,1 3,4
1124 3b0f3d61 2020-01-22 neels * -2 | 0,2__
1125 3b0f3d61 2020-01-22 neels * | x == 0
1127 3b0f3d61 2020-01-22 neels debug("prev[k-1] = %d,%d prev[k+1] = %d,%d\n",
1128 3b0f3d61 2020-01-22 neels kd_prev_column[k-1], xk_to_y(kd_prev_column[k-1],k-1),
1129 3b0f3d61 2020-01-22 neels kd_prev_column[k+1], xk_to_y(kd_prev_column[k+1],k+1));
1130 3b0f3d61 2020-01-22 neels if (y == 0
1131 0d27172a 2020-05-06 neels || (x > 0
1132 0d27172a 2020-05-06 neels && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1133 3b0f3d61 2020-01-22 neels k = k - 1;
1134 3b0f3d61 2020-01-22 neels debug("prev k=k-1=%d x=%d y=%d\n",
1135 0d27172a 2020-05-06 neels k, kd_prev_column[k],
1136 0d27172a 2020-05-06 neels xk_to_y(kd_prev_column[k], k));
1138 3b0f3d61 2020-01-22 neels k = k + 1;
1139 3b0f3d61 2020-01-22 neels debug("prev k=k+1=%d x=%d y=%d\n",
1140 0d27172a 2020-05-06 neels k, kd_prev_column[k],
1141 0d27172a 2020-05-06 neels xk_to_y(kd_prev_column[k], k));
1143 3b0f3d61 2020-01-22 neels kd_column = kd_prev_column;
1146 3b0f3d61 2020-01-22 neels /* Forwards again, this time recording the diff chunks.
1147 0d27172a 2020-05-06 neels * Definitely start from 0,0. kd_column[0] may actually point to the
1148 0d27172a 2020-05-06 neels * bottom of a snake starting at 0,0 */
1152 3b0f3d61 2020-01-22 neels kd_column = kd_origin;
1153 3b0f3d61 2020-01-22 neels for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1154 3b0f3d61 2020-01-22 neels int next_x = kd_column[0];
1155 3b0f3d61 2020-01-22 neels int next_y = kd_column[1];
1156 3b0f3d61 2020-01-22 neels debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1157 3b0f3d61 2020-01-22 neels x, y, next_x, next_y);
1159 3b0f3d61 2020-01-22 neels struct diff_atom *left_atom = &left->atoms.head[x];
1160 3b0f3d61 2020-01-22 neels int left_section_len = next_x - x;
1161 3b0f3d61 2020-01-22 neels struct diff_atom *right_atom = &right->atoms.head[y];
1162 3b0f3d61 2020-01-22 neels int right_section_len = next_y - y;
1164 3b0f3d61 2020-01-22 neels rc = DIFF_RC_ENOMEM;
1165 3b0f3d61 2020-01-22 neels if (left_section_len && right_section_len) {
1166 3b0f3d61 2020-01-22 neels /* This must be a snake slide.
1167 0d27172a 2020-05-06 neels * Snake slides have a straight line leading into them
1168 0d27172a 2020-05-06 neels * (except when starting at (0,0)). Find out whether the
1169 0d27172a 2020-05-06 neels * lead-in is horizontal or vertical:
1172 3b0f3d61 2020-01-22 neels * ---------->
1174 3b0f3d61 2020-01-22 neels * r| o-o o
1181 0d27172a 2020-05-06 neels * If left_section_len > right_section_len, the lead-in
1182 0d27172a 2020-05-06 neels * is horizontal, meaning first remove one atom from the
1183 0d27172a 2020-05-06 neels * left before sliding down the snake.
1184 0d27172a 2020-05-06 neels * If right_section_len > left_section_len, the lead-in
1185 0d27172a 2020-05-06 neels * is vetical, so add one atom from the right before
1186 0d27172a 2020-05-06 neels * sliding down the snake. */
1187 3b0f3d61 2020-01-22 neels if (left_section_len == right_section_len + 1) {
1188 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1189 3b0f3d61 2020-01-22 neels left_atom, 1,
1190 3b0f3d61 2020-01-22 neels right_atom, 0))
1191 3b0f3d61 2020-01-22 neels goto return_rc;
1192 3b0f3d61 2020-01-22 neels left_atom++;
1193 3b0f3d61 2020-01-22 neels left_section_len--;
1194 3b0f3d61 2020-01-22 neels } else if (right_section_len == left_section_len + 1) {
1195 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1196 3b0f3d61 2020-01-22 neels left_atom, 0,
1197 3b0f3d61 2020-01-22 neels right_atom, 1))
1198 3b0f3d61 2020-01-22 neels goto return_rc;
1199 3b0f3d61 2020-01-22 neels right_atom++;
1200 3b0f3d61 2020-01-22 neels right_section_len--;
1201 3b0f3d61 2020-01-22 neels } else if (left_section_len != right_section_len) {
1202 0d27172a 2020-05-06 neels /* The numbers are making no sense. Should never
1203 0d27172a 2020-05-06 neels * happen. */
1204 3b0f3d61 2020-01-22 neels rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1205 3b0f3d61 2020-01-22 neels goto return_rc;
1208 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1209 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1210 0d27172a 2020-05-06 neels right_atom,
1211 0d27172a 2020-05-06 neels right_section_len))
1212 3b0f3d61 2020-01-22 neels goto return_rc;
1213 3b0f3d61 2020-01-22 neels } else if (left_section_len && !right_section_len) {
1214 0d27172a 2020-05-06 neels /* Only left atoms and none on the right, they form a
1215 0d27172a 2020-05-06 neels * "minus" chunk, then. */
1216 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1217 3b0f3d61 2020-01-22 neels left_atom, left_section_len,
1218 3b0f3d61 2020-01-22 neels right_atom, 0))
1219 3b0f3d61 2020-01-22 neels goto return_rc;
1220 3b0f3d61 2020-01-22 neels } else if (!left_section_len && right_section_len) {
1221 0d27172a 2020-05-06 neels /* No left atoms, only atoms on the right, they form a
1222 0d27172a 2020-05-06 neels * "plus" chunk, then. */
1223 3b0f3d61 2020-01-22 neels if (!diff_state_add_chunk(state, true,
1224 3b0f3d61 2020-01-22 neels left_atom, 0,
1225 0d27172a 2020-05-06 neels right_atom,
1226 0d27172a 2020-05-06 neels right_section_len))
1227 3b0f3d61 2020-01-22 neels goto return_rc;
1230 3b0f3d61 2020-01-22 neels x = next_x;
1231 3b0f3d61 2020-01-22 neels y = next_y;
1234 3b0f3d61 2020-01-22 neels rc = DIFF_RC_OK;
1236 3b0f3d61 2020-01-22 neels return_rc:
1237 3b0f3d61 2020-01-22 neels free(kd_buf);
1238 3b0f3d61 2020-01-22 neels debug("** END %s rc=%d\n", __func__, rc);
1239 3b0f3d61 2020-01-22 neels return rc;
