1 /* Myers diff algorithm implementation, invented by Eugene W. Myers [1].
2 * Implementations of both the Myers Divide Et Impera (using linear space)
3 * and the canonical Myers algorithm (using quadratic space). */
5 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 #include <diff/diff_main.h>
24 /* Myers' diff algorithm [1] is nicely explained in [2].
25 * [1] http://www.xmailserver.org/diff2.pdf
26 * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
28 * Myers approaches finding the smallest diff as a graph problem.
29 * The crux is that the original algorithm requires quadratic amount of memory:
30 * both sides' lengths added, and that squared. So if we're diffing lines of text, two files with 1000 lines each would
31 * blow up to a matrix of about 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
32 * The solution is using Myers' "divide and conquer" extension algorithm, which does the original traversal from both
33 * ends of the files to reach a middle where these "snakes" touch, hence does not need to backtrace the traversal, and
34 * so gets away with only keeping a single column of that huge state matrix in memory.
36 * Todo: the divide and conquer requires linear *space*, not necessarily linear *time*. It recurses, apparently doing
37 * multiple Myers passes, and also it apparently favors fragmented diffs in cases where chunks of text were moved to a
38 * different place. Up to a given count of diff atoms (text lines), it might be desirable to accept the quadratic memory
39 * usage, get nicer diffs and less re-iteration of the same data?
43 unsigned int left_start;
44 unsigned int left_end;
45 unsigned int right_start;
46 unsigned int right_end;
49 #define diff_box_empty(DIFF_SNAKE) ((DIFF_SNAKE)->left_end == 0)
52 /* If the two contents of a file are A B C D E and X B C Y,
53 * the Myers diff graph looks like:
71 * Moving right means delete an atom from the left-hand-side,
72 * Moving down means add an atom from the right-hand-side.
73 * Diagonals indicate identical atoms on both sides, the challenge is to use as many diagonals as possible.
75 * The original Myers algorithm walks all the way from the top left to the bottom right, remembers all steps, and then
76 * backtraces to find the shortest path. However, that requires keeping the entire graph in memory, which needs
79 * Myers adds a variant that uses linear space -- note, not linear time, only linear space: walk forward and backward,
80 * find a meeting point in the middle, and recurse on the two separate sections. This is called "divide and conquer".
82 * d: the step number, starting with 0, a.k.a. the distance from the starting point.
83 * k: relative index in the state array for the forward scan, indicating on which diagonal through the diff graph we
85 * c: relative index in the state array for the backward scan, indicating the diagonal number from the bottom up.
87 * The "divide and conquer" traversal through the Myers graph looks like this:
90 * ----+--------------------------------------------
98 * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
100 * 0 | -->0,0 3,3 4,4 -1
102 * -1 | 0,1 1,2 3,4 -2
107 * | forward-> <-backward
109 * x,y pairs here are the coordinates in the Myers graph:
110 * x = atom index in left-side source, y = atom index in the right-side source.
112 * Only one forward column and one backward column are kept in mem, each need at most left.len + 1 + right.len items.
113 * Note that each d step occupies either the even or the odd items of a column: if e.g. the previous column is in the
114 * odd items, the next column is formed in the even items, without overwriting the previous column's results.
116 * Also note that from the diagonal index k and the x coordinate, the y coordinate can be derived:
118 * Hence the state array only needs to keep the x coordinate, i.e. the position in the left-hand file, and the y
119 * coordinate, i.e. position in the right-hand file, is derived from the index in the state array.
121 * The two traces meet at 4,3, the first step (here found in the forward traversal) where a forward position is on or
122 * past a backward traced position on the same diagonal.
124 * This divides the problem space into:
134 * 3 o-o-o-o-*-o *: forward and backward meet here
138 * Doing the same on each section lead to:
144 * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
145 * B \ f: then forward d=2 reaches here (sliding down the snake)
146 * 2 o As result, the box from b to f is found to be identical;
147 * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial tail 3,3 to 4,3.
152 * 4 o *: forward and backward meet here
154 * and solving the last top left box gives:
170 #define xk_to_y(X, K) ((X) - (K))
171 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
172 #define k_to_c(K, DELTA) ((K) + (DELTA))
173 #define c_to_k(C, DELTA) ((C) - (DELTA))
175 /* Do one forwards step in the "divide and conquer" graph traversal.
176 * left: the left side to diff.
177 * right: the right side to diff against.
178 * kd_forward: the traversal state for forwards traversal, modified by this function.
179 * This is carried over between invocations with increasing d.
180 * kd_forward points at the center of the state array, allowing negative indexes.
181 * kd_backward: the traversal state for backwards traversal, to find a meeting point.
182 * Since forwards is done first, kd_backward will be valid for d - 1, not d.
183 * kd_backward points at the center of the state array, allowing negative indexes.
184 * d: Step or distance counter, indicating for what value of d the kd_forward should be populated.
185 * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should be for d == 0.
186 * meeting_snake: resulting meeting point, if any.
189 diff_divide_myers_forward(struct diff_data *left, struct diff_data *right,
190 int *kd_forward, int *kd_backward, int d,
191 struct diff_box *meeting_snake)
193 int delta = (int)right->atoms.len - (int)left->atoms.len;
197 debug("-- %s d=%d\n", __func__, d);
199 for (k = d; k >= -d; k -= 2) {
200 if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
201 /* This diagonal is completely outside of the Myers graph, don't calculate it. */
202 if (k < -(int)right->atoms.len)
203 debug(" %d k < -(int)right->atoms.len %d\n", k, -(int)right->atoms.len);
205 debug(" %d k > left->atoms.len %d\n", k, left->atoms.len);
207 /* We are traversing negatively, and already below the entire graph, nothing will come
215 debug("- k = %d\n", k);
217 /* This is the initializing step. There is no prev_k yet, get the initial x from the top left of
218 * the Myers graph. */
221 /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
222 * For this, all k should derive from k - 1, only the bottom most k derive from k + 1:
225 * ----+----------------
227 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
233 * -1 | 0,1 <-- bottom most for d=1 from prev_k = -1 + 1 = 0
235 * -2 | 0,2 <-- bottom most for d=2 from prev_k = -2 + 1 = -1
237 * Except when a k + 1 from a previous run already means a further advancement in the graph.
238 * If k == d, there is no k + 1 and k - 1 is the only option.
239 * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph.
241 else if (k > -d && (k == d
242 || (k - 1 >= -(int)right->atoms.len
243 && kd_forward[k - 1] >= kd_forward[k + 1]))) {
244 /* Advance from k - 1.
245 * From position prev_k, step to the right in the Myers graph: x += 1.
248 int prev_x = kd_forward[prev_k];
251 /* The bottom most one.
252 * From position prev_k, step to the bottom in the Myers graph: y += 1.
253 * Incrementing y is achieved by decrementing k while keeping the same x.
254 * (since we're deriving y from y = x - k).
257 int prev_x = kd_forward[prev_k];
261 int x_before_slide = x;
262 /* Slide down any snake that we might find here. */
263 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len
264 && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)]))
267 if (x_before_slide != x) {
268 debug(" down %d similar lines\n", x - x_before_slide);
273 for (fi = d; fi >= k; fi--) {
274 debug("kd_forward[%d] = (%d, %d)\n", fi, kd_forward[fi], kd_forward[fi] - fi);
276 if (kd_forward[fi] >= 0 && kd_forward[fi] < left->atoms.len)
277 debug_dump_atom(left, right, &left->atoms.head[kd_forward[fi]]);
280 if (kd_forward[fi]-fi >= 0 && kd_forward[fi]-fi < right->atoms.len)
281 debug_dump_atom(right, left, &right->atoms.head[kd_forward[fi]-fi]);
288 if (x < 0 || x > left->atoms.len
289 || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
292 /* Figured out a new forwards traversal, see if this has gone onto or even past a preceding backwards
295 * If the delta in length is odd, then d and backwards_d hit the same state indexes:
297 * ----+---------------- ----------------
307 * 0 | -->0,0 3,3====4,4 -1
314 * If the delta is even, they end up off-by-one, i.e. on different diagonals:
317 * ----+---------------- ----------------
325 * 0 | -->0,0 3,3 4,4<-- 0
332 * So in the forward path, we can only match up diagonals when the delta is odd.
334 if ((delta & 1) == 0)
336 /* Forwards is done first, so the backwards one was still at d - 1. Can't do this for d == 0. */
337 int backwards_d = d - 1;
341 debug("backwards_d = %d\n", backwards_d);
343 /* If both sides have the same length, forward and backward start on the same diagonal, meaning the
344 * backwards state index c == k.
345 * As soon as the lengths are not the same, the backwards traversal starts on a different diagonal, and
346 * c = k shifted by the difference in length.
348 int c = k_to_c(k, delta);
350 /* When the file sizes are very different, the traversal trees start on far distant diagonals.
351 * They don't necessarily meet straight on. See whether this forward value is on a diagonal that
352 * is also valid in kd_backward[], and match them if so. */
353 if (c >= -backwards_d && c <= backwards_d) {
354 /* Current k is on a diagonal that exists in kd_backward[]. If the two x positions have
355 * met or passed (forward walked onto or past backward), then we've found a midpoint / a
358 * When forwards and backwards traversals meet, the endpoints of the mid-snake are
359 * not the two points in kd_forward and kd_backward, but rather the section that
360 * was slid (if any) of the current forward/backward traversal only.
384 * The forward traversal reached M from the top and slid downwards to A.
385 * The backward traversal already reached X, which is not a straight line from M
386 * anymore, so picking a mid-snake from M to X would yield a mistake.
388 * The correct mid-snake is between M and A. M is where the forward traversal hit
389 * the diagonal that the backward traversal has already passed, and A is what it
390 * reaches when sliding down identical lines.
392 int backward_x = kd_backward[c];
393 debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
394 k, c, x, xk_to_y(x, k), backward_x, xc_to_y(backward_x, c, delta));
395 if (x >= backward_x) {
396 *meeting_snake = (struct diff_box){
397 .left_start = x_before_slide,
399 .right_start = xc_to_y(x_before_slide, c, delta),
400 .right_end = xk_to_y(x, k),
402 debug("HIT x=(%u,%u) - y=(%u,%u)\n",
403 meeting_snake->left_start,
404 meeting_snake->right_start,
405 meeting_snake->left_end,
406 meeting_snake->right_end);
407 debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
413 debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d-1);
417 /* Do one backwards step in the "divide and conquer" graph traversal.
418 * left: the left side to diff.
419 * right: the right side to diff against.
420 * kd_forward: the traversal state for forwards traversal, to find a meeting point.
421 * Since forwards is done first, after this, both kd_forward and kd_backward will be valid for d.
422 * kd_forward points at the center of the state array, allowing negative indexes.
423 * kd_backward: the traversal state for backwards traversal, to find a meeting point.
424 * This is carried over between invocations with increasing d.
425 * kd_backward points at the center of the state array, allowing negative indexes.
426 * d: Step or distance counter, indicating for what value of d the kd_backward should be populated.
427 * Before the first invocation, kd_backward[0] shall point at the bottom right of the Myers graph
428 * (left.len, right.len).
429 * The first invocation will be for d == 1.
430 * meeting_snake: resulting meeting point, if any.
433 diff_divide_myers_backward(struct diff_data *left, struct diff_data *right,
434 int *kd_forward, int *kd_backward, int d,
435 struct diff_box *meeting_snake)
437 int delta = (int)right->atoms.len - (int)left->atoms.len;
441 debug("-- %s d=%d\n", __func__, d);
443 for (c = d; c >= -d; c -= 2) {
444 if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
445 /* This diagonal is completely outside of the Myers graph, don't calculate it. */
446 if (c < -(int)left->atoms.len)
447 debug(" %d c < -(int)left->atoms.len %d\n", c, -(int)left->atoms.len);
449 debug(" %d c > right->atoms.len %d\n", c, right->atoms.len);
451 /* We are traversing negatively, and already below the entire graph, nothing will come
459 debug("- c = %d\n", c);
461 /* This is the initializing step. There is no prev_c yet, get the initial x from the bottom
462 * right of the Myers graph. */
465 /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
466 * For this, all c should derive from c - 1, only the bottom most c derive from c + 1:
469 * ---------------------------------------------------
473 * from prev_c = c - 1 --> 5,2 2
479 * bottom most for d=1 from c + 1 --> 4,4 -1
481 * bottom most for d=2 --> 3,4 -2
483 * Except when a c + 1 from a previous run already means a further advancement in the graph.
484 * If c == d, there is no c + 1 and c - 1 is the only option.
485 * If c < d, use c + 1 in case that yields a larger x. Also use c + 1 if c - 1 is outside the graph.
487 else if (c > -d && (c == d
488 || (c - 1 >= -(int)right->atoms.len
489 && kd_backward[c - 1] <= kd_backward[c + 1]))) {
491 * From position prev_c, step upwards in the Myers graph: y -= 1.
492 * Decrementing y is achieved by incrementing c while keeping the same x.
493 * (since we're deriving y from y = x - c + delta).
496 int prev_x = kd_backward[prev_c];
499 /* The bottom most one.
500 * From position prev_c, step to the left in the Myers graph: x -= 1.
503 int prev_x = kd_backward[prev_c];
507 /* Slide up any snake that we might find here (sections of identical lines on both sides). */
508 debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c, delta), xc_to_y(x, c, delta)-1);
510 debug(" l="); debug_dump_atom(left, right, &left->atoms.head[x-1]);
512 if (xc_to_y(x, c, delta) > 0) {
513 debug(" r="); debug_dump_atom(right, left, &right->atoms.head[xc_to_y(x, c, delta)-1]);
515 int x_before_slide = x;
516 while (x > 0 && xc_to_y(x, c, delta) > 0
517 && diff_atom_same(&left->atoms.head[x-1], &right->atoms.head[xc_to_y(x, c, delta)-1]))
520 if (x_before_slide != x) {
521 debug(" up %d similar lines\n", x_before_slide - x);
526 for (fi = d; fi >= c; fi--) {
527 debug("kd_backward[%d] = (%d, %d)\n", fi, kd_backward[fi],
528 kd_backward[fi] - fi + delta);
530 if (kd_backward[fi] >= 0 && kd_backward[fi] < left->atoms.len)
531 debug_dump_atom(left, right, &left->atoms.head[kd_backward[fi]]);
534 if (kd_backward[fi]-fi+delta >= 0 && kd_backward[fi]-fi+delta < right->atoms.len)
535 debug_dump_atom(right, left, &right->atoms.head[kd_backward[fi]-fi+delta]);
542 if (x < 0 || x > left->atoms.len
543 || xc_to_y(x, c, delta) < 0 || xc_to_y(x, c, delta) > right->atoms.len)
546 /* Figured out a new backwards traversal, see if this has gone onto or even past a preceding forwards
549 * If the delta in length is even, then d and backwards_d hit the same state indexes -- note how this is
550 * different from in the forwards traversal, because now both d are the same:
553 * ----+---------------- --------------------
563 * 0 | -->0,0 3,3====4,3 5,4<-- 0
570 * If the delta is odd, they end up off-by-one, i.e. on different diagonals.
571 * So in the backward path, we can only match up diagonals when the delta is even.
573 if ((delta & 1) == 0) {
574 /* Forwards was done first, now both d are the same. */
577 /* As soon as the lengths are not the same, the backwards traversal starts on a different diagonal, and
578 * c = k shifted by the difference in length.
580 int k = c_to_k(c, delta);
582 /* When the file sizes are very different, the traversal trees start on far distant diagonals.
583 * They don't necessarily meet straight on. See whether this backward value is also on a valid
584 * diagonal in kd_forward[], and match them if so. */
585 if (k >= -forwards_d && k <= forwards_d) {
586 /* Current c is on a diagonal that exists in kd_forward[]. If the two x positions have
587 * met or passed (backward walked onto or past forward), then we've found a midpoint / a
590 * When forwards and backwards traversals meet, the endpoints of the mid-snake are
591 * not the two points in kd_forward and kd_backward, but rather the section that
592 * was slid (if any) of the current forward/backward traversal only.
614 * The backward traversal reached M from the bottom and slid upwards.
615 * The forward traversal already reached X, which is not a straight line from M
616 * anymore, so picking a mid-snake from M to X would yield a mistake.
618 * The correct mid-snake is between M and A. M is where the backward traversal hit
619 * the diagonal that the forwards traversal has already passed, and A is what it
620 * reaches when sliding up identical lines.
623 int forward_x = kd_forward[k];
624 debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
625 k, c, forward_x, xk_to_y(forward_x, k), x, xc_to_y(x, c, delta));
626 if (forward_x >= x) {
627 *meeting_snake = (struct diff_box){
629 .left_end = x_before_slide,
630 .right_start = xc_to_y(x, c, delta),
631 .right_end = xk_to_y(x_before_slide, k),
633 debug("HIT x=%u,%u - y=%u,%u\n",
634 meeting_snake->left_start,
635 meeting_snake->right_start,
636 meeting_snake->left_end,
637 meeting_snake->right_end);
638 debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
644 debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward, d);
648 /* Myers "Divide et Impera": tracing forwards from the start and backwards from the end to find a midpoint that divides
649 * the problem into smaller chunks. Requires only linear amounts of memory. */
651 diff_algo_myers_divide(const struct diff_algo_config *algo_config, struct diff_state *state)
653 enum diff_rc rc = DIFF_RC_ENOMEM;
654 struct diff_data *left = &state->left;
655 struct diff_data *right = &state->right;
657 debug("\n** %s\n", __func__);
662 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
664 /* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
665 unsigned int max = left->atoms.len + right->atoms.len;
666 size_t kd_len = max + 1;
667 size_t kd_buf_size = kd_len << 1;
668 int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
670 return DIFF_RC_ENOMEM;
672 for (i = 0; i < kd_buf_size; i++)
674 int *kd_forward = kd_buf;
675 int *kd_backward = kd_buf + kd_len;
677 /* The 'k' axis in Myers spans positive and negative indexes, so point the kd to the middle.
678 * It is then possible to index from -max/2 .. max/2. */
680 kd_backward += max/2;
683 struct diff_box mid_snake = {};
684 bool found_midpoint = false;
685 for (d = 0; d <= (max/2); d++) {
686 debug("-- d=%d\n", d);
687 found_midpoint = diff_divide_myers_forward(left, right, kd_forward, kd_backward, d, &mid_snake);
690 found_midpoint = diff_divide_myers_backward(left, right, kd_forward, kd_backward, d, &mid_snake);
695 if (!found_midpoint) {
696 /* Divide and conquer failed to find a meeting point. Use the fallback_algo defined in the algo_config
697 * (leave this to the caller). This is just paranoia/sanity, we normally should always find a midpoint.
699 debug(" no midpoint \n");
700 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
703 debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
704 mid_snake.left_start, mid_snake.left_end, left->atoms.len,
705 mid_snake.right_start, mid_snake.right_end, right->atoms.len);
707 /* Section before the mid-snake. */
708 debug("Section before the mid-snake\n");
710 struct diff_atom *left_atom = &left->atoms.head[0];
711 unsigned int left_section_len = mid_snake.left_start;
712 struct diff_atom *right_atom = &right->atoms.head[0];
713 unsigned int right_section_len = mid_snake.right_start;
715 if (left_section_len && right_section_len) {
716 /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
717 if (!diff_state_add_chunk(state, false,
718 left_atom, left_section_len,
719 right_atom, right_section_len))
721 } else if (left_section_len && !right_section_len) {
722 /* Only left atoms and none on the right, they form a "minus" chunk, then. */
723 if (!diff_state_add_chunk(state, true,
724 left_atom, left_section_len,
727 } else if (!left_section_len && right_section_len) {
728 /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
729 if (!diff_state_add_chunk(state, true,
731 right_atom, right_section_len))
734 /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing before the mid-snake. */
736 if (!diff_box_empty(&mid_snake)) {
737 /* The midpoint is a "snake", i.e. on a section of identical data on both sides: that
738 * section immediately becomes a solved diff chunk. */
739 debug("the mid-snake\n");
740 if (!diff_state_add_chunk(state, true,
741 &left->atoms.head[mid_snake.left_start],
742 mid_snake.left_end - mid_snake.left_start,
743 &right->atoms.head[mid_snake.right_start],
744 mid_snake.right_end - mid_snake.right_start))
748 /* Section after the mid-snake. */
749 debug("Section after the mid-snake\n");
750 debug(" left_end %u right_end %u\n", mid_snake.left_end, mid_snake.right_end);
751 debug(" left_count %u right_count %u\n", left->atoms.len, right->atoms.len);
752 left_atom = &left->atoms.head[mid_snake.left_end];
753 left_section_len = left->atoms.len - mid_snake.left_end;
754 right_atom = &right->atoms.head[mid_snake.right_end];
755 right_section_len = right->atoms.len - mid_snake.right_end;
757 if (left_section_len && right_section_len) {
758 /* Record an unsolved chunk, the caller will apply inner_algo() on this chunk. */
759 if (!diff_state_add_chunk(state, false,
760 left_atom, left_section_len,
761 right_atom, right_section_len))
763 } else if (left_section_len && !right_section_len) {
764 /* Only left atoms and none on the right, they form a "minus" chunk, then. */
765 if (!diff_state_add_chunk(state, true,
766 left_atom, left_section_len,
769 } else if (!left_section_len && right_section_len) {
770 /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
771 if (!diff_state_add_chunk(state, true,
773 right_atom, right_section_len))
776 /* else: left_section_len == 0 and right_section_len == 0, i.e. nothing after the mid-snake. */
783 debug("** END %s\n", __func__);
787 /* Myers Diff tracing from the start all the way through to the end, requiring quadratic amounts of memory. This can
788 * fail if the required space surpasses algo_config->permitted_state_size. */
790 diff_algo_myers(const struct diff_algo_config *algo_config, struct diff_state *state)
792 /* do a diff_divide_myers_forward() without a _backward(), so that it walks forward across the entire
793 * files to reach the end. Keep each run's state, and do a final backtrace. */
794 enum diff_rc rc = DIFF_RC_ENOMEM;
795 struct diff_data *left = &state->left;
796 struct diff_data *right = &state->right;
798 debug("\n** %s\n", __func__);
803 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
805 /* Allocate two columns of a Myers graph, one for the forward and one for the backward traversal. */
806 unsigned int max = left->atoms.len + right->atoms.len;
807 size_t kd_len = max + 1 + max;
808 size_t kd_buf_size = kd_len * kd_len;
809 size_t kd_state_size = kd_buf_size * sizeof(int);
810 debug("state size: %zu\n", kd_buf_size);
811 if (kd_buf_size < kd_len /* overflow? */
812 || kd_state_size > algo_config->permitted_state_size) {
813 debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
814 kd_state_size, algo_config->permitted_state_size);
815 return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
818 int *kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int));
820 return DIFF_RC_ENOMEM;
822 for (i = 0; i < kd_buf_size; i++)
825 /* The 'k' axis in Myers spans positive and negative indexes, so point the kd to the middle.
826 * It is then possible to index from -max .. max. */
827 int *kd_origin = kd_buf + max;
828 int *kd_column = kd_origin;
831 int backtrack_d = -1;
835 for (d = 0; d <= max; d++, kd_column += kd_len) {
836 debug("-- d=%d\n", d);
838 debug("-- %s d=%d\n", __func__, d);
840 for (k = d; k >= -d; k -= 2) {
841 if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
842 /* This diagonal is completely outside of the Myers graph, don't calculate it. */
843 if (k < -(int)right->atoms.len)
844 debug(" %d k < -(int)right->atoms.len %d\n", k, -(int)right->atoms.len);
846 debug(" %d k > left->atoms.len %d\n", k, left->atoms.len);
848 /* We are traversing negatively, and already below the entire graph, nothing will come
857 debug("- k = %d\n", k);
859 /* This is the initializing step. There is no prev_k yet, get the initial x from the top left of
860 * the Myers graph. */
863 int *kd_prev_column = kd_column - kd_len;
865 /* Favoring "-" lines first means favoring moving rightwards in the Myers graph.
866 * For this, all k should derive from k - 1, only the bottom most k derive from k + 1:
869 * ----+----------------
871 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
877 * -1 | 0,1 <-- bottom most for d=1 from prev_k = -1 + 1 = 0
879 * -2 | 0,2 <-- bottom most for d=2 from prev_k = -2 + 1 = -1
881 * Except when a k + 1 from a previous run already means a further advancement in the graph.
882 * If k == d, there is no k + 1 and k - 1 is the only option.
883 * If k < d, use k + 1 in case that yields a larger x. Also use k + 1 if k - 1 is outside the graph.
885 if (k > -d && (k == d
886 || (k - 1 >= -(int)right->atoms.len
887 && kd_prev_column[k - 1] >= kd_prev_column[k + 1]))) {
888 /* Advance from k - 1.
889 * From position prev_k, step to the right in the Myers graph: x += 1.
892 int prev_x = kd_prev_column[prev_k];
895 /* The bottom most one.
896 * From position prev_k, step to the bottom in the Myers graph: y += 1.
897 * Incrementing y is achieved by decrementing k while keeping the same x.
898 * (since we're deriving y from y = x - k).
901 int prev_x = kd_prev_column[prev_k];
906 /* Slide down any snake that we might find here. */
907 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len
908 && diff_atom_same(&left->atoms.head[x], &right->atoms.head[xk_to_y(x, k)]))
914 for (fi = d; fi >= k; fi-=2) {
915 debug("kd_column[%d] = (%d, %d)\n", fi, kd_column[fi], kd_column[fi] - fi);
917 if (kd_column[fi] >= 0 && kd_column[fi] < left->atoms.len)
918 debug_dump_atom(left, right, &left->atoms.head[kd_column[fi]]);
921 if (kd_column[fi]-fi >= 0 && kd_column[fi]-fi < right->atoms.len)
922 debug_dump_atom(right, left, &right->atoms.head[kd_column[fi]-fi]);
929 if (x == left->atoms.len && xk_to_y(x, k) == right->atoms.len) {
933 debug("Reached the end at d = %d, k = %d\n",
934 backtrack_d, backtrack_k);
939 if (backtrack_d >= 0)
943 debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
945 /* backtrack. A matrix spanning from start to end of the file is ready:
948 * ----+---------------------------------
956 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
963 * From (4,4) backwards, find the previous position that is the largest, and remember it.
966 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
970 /* When the best position is identified, remember it for that kd_column.
971 * That kd_column is no longer needed otherwise, so just re-purpose kd_column[0] = x and kd_column[1] = y,
972 * so that there is no need to allocate more memory.
976 debug("Backtrack d=%d: xy=(%d, %d)\n",
977 d, kd_column[0], kd_column[1]);
979 /* Don't access memory before kd_buf */
982 int *kd_prev_column = kd_column - kd_len;
984 /* When y == 0, backtracking downwards (k-1) is the only way.
985 * When x == 0, backtracking upwards (k+1) is the only way.
988 * ----+---------------------------------
996 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
1003 debug("prev[k-1] = %d,%d prev[k+1] = %d,%d\n",
1004 kd_prev_column[k-1], xk_to_y(kd_prev_column[k-1],k-1),
1005 kd_prev_column[k+1], xk_to_y(kd_prev_column[k+1],k+1));
1007 || (x > 0 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1009 debug("prev k=k-1=%d x=%d y=%d\n",
1010 k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k));
1013 debug("prev k=k+1=%d x=%d y=%d\n",
1014 k, kd_prev_column[k], xk_to_y(kd_prev_column[k], k));
1016 kd_column = kd_prev_column;
1019 /* Forwards again, this time recording the diff chunks.
1020 * Definitely start from 0,0. kd_column[0] may actually point to the bottom of a snake starting at 0,0 */
1024 kd_column = kd_origin;
1025 for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1026 int next_x = kd_column[0];
1027 int next_y = kd_column[1];
1028 debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1029 x, y, next_x, next_y);
1031 struct diff_atom *left_atom = &left->atoms.head[x];
1032 int left_section_len = next_x - x;
1033 struct diff_atom *right_atom = &right->atoms.head[y];
1034 int right_section_len = next_y - y;
1036 rc = DIFF_RC_ENOMEM;
1037 if (left_section_len && right_section_len) {
1038 /* This must be a snake slide.
1039 * Snake slides have a straight line leading into them (except when starting at (0,0)). Find
1040 * out whether the lead-in is horizontal or vertical:
1052 * If left_section_len > right_section_len, the lead-in is horizontal, meaning first
1053 * remove one atom from the left before sliding down the snake.
1054 * If right_section_len > left_section_len, the lead-in is vetical, so add one atom from
1055 * the right before sliding down the snake. */
1056 if (left_section_len == right_section_len + 1) {
1057 if (!diff_state_add_chunk(state, true,
1063 } else if (right_section_len == left_section_len + 1) {
1064 if (!diff_state_add_chunk(state, true,
1069 right_section_len--;
1070 } else if (left_section_len != right_section_len) {
1071 /* The numbers are making no sense. Should never happen. */
1072 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1076 if (!diff_state_add_chunk(state, true,
1077 left_atom, left_section_len,
1078 right_atom, right_section_len))
1080 } else if (left_section_len && !right_section_len) {
1081 /* Only left atoms and none on the right, they form a "minus" chunk, then. */
1082 if (!diff_state_add_chunk(state, true,
1083 left_atom, left_section_len,
1086 } else if (!left_section_len && right_section_len) {
1087 /* No left atoms, only atoms on the right, they form a "plus" chunk, then. */
1088 if (!diff_state_add_chunk(state, true,
1090 right_atom, right_section_len))
1102 debug("** END %s rc=%d\n", __func__, rc);
