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