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.
27 #include <arraylist.h>
28 #include <diff_main.h>
30 #include "diff_internal.h"
31 #include "diff_debug.h"
33 /* Myers' diff algorithm [1] is nicely explained in [2].
34 * [1] http://www.xmailserver.org/diff2.pdf
35 * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
37 * Myers approaches finding the smallest diff as a graph problem.
38 * The crux is that the original algorithm requires quadratic amount of memory:
39 * both sides' lengths added, and that squared. So if we're diffing lines of
40 * text, two files with 1000 lines each would blow up to a matrix of about
41 * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
42 * The solution is using Myers' "divide and conquer" extension algorithm, which
43 * does the original traversal from both ends of the files to reach a middle
44 * where these "snakes" touch, hence does not need to backtrace the traversal,
45 * and so gets away with only keeping a single column of that huge state matrix
50 unsigned int left_start;
51 unsigned int left_end;
52 unsigned int right_start;
53 unsigned int right_end;
56 /* If the two contents of a file are A B C D E and X B C Y,
57 * the Myers diff graph looks like:
75 * Moving right means delete an atom from the left-hand-side,
76 * Moving down means add an atom from the right-hand-side.
77 * Diagonals indicate identical atoms on both sides, the challenge is to use as
78 * many diagonals as possible.
80 * The original Myers algorithm walks all the way from the top left to the
81 * bottom right, remembers all steps, and then backtraces to find the shortest
82 * path. However, that requires keeping the entire graph in memory, which needs
85 * Myers adds a variant that uses linear space -- note, not linear time, only
86 * linear space: walk forward and backward, find a meeting point in the middle,
87 * and recurse on the two separate sections. This is called "divide and
90 * d: the step number, starting with 0, a.k.a. the distance from the starting
92 * k: relative index in the state array for the forward scan, indicating on
93 * which diagonal through the diff graph we currently are.
94 * c: relative index in the state array for the backward scan, indicating the
95 * diagonal number from the bottom up.
97 * The "divide and conquer" traversal through the Myers graph looks like this:
100 * ----+--------------------------------------------
108 * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
110 * 0 | -->0,0 3,3 4,4 -1
112 * -1 | 0,1 1,2 3,4 -2
117 * | forward-> <-backward
119 * x,y pairs here are the coordinates in the Myers graph:
120 * x = atom index in left-side source, y = atom index in the right-side source.
122 * Only one forward column and one backward column are kept in mem, each need at
123 * most left.len + 1 + right.len items. Note that each d step occupies either
124 * the even or the odd items of a column: if e.g. the previous column is in the
125 * odd items, the next column is formed in the even items, without overwriting
126 * the previous column's results.
128 * Also note that from the diagonal index k and the x coordinate, the y
129 * coordinate can be derived:
131 * Hence the state array only needs to keep the x coordinate, i.e. the position
132 * in the left-hand file, and the y coordinate, i.e. position in the right-hand
133 * file, is derived from the index in the state array.
135 * The two traces meet at 4,3, the first step (here found in the forward
136 * traversal) where a forward position is on or past a backward traced position
137 * on the same diagonal.
139 * This divides the problem space into:
149 * 3 o-o-o-o-*-o *: forward and backward meet here
153 * Doing the same on each section lead to:
159 * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
160 * B \ f: then forward d=2 reaches here (sliding down the snake)
161 * 2 o As result, the box from b to f is found to be identical;
162 * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial
163 * 3 f-o tail 3,3 to 4,3.
167 * 4 o *: forward and backward meet here
169 * and solving the last top left box gives:
185 #define xk_to_y(X, K) ((X) - (K))
186 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
187 #define k_to_c(K, DELTA) ((K) + (DELTA))
188 #define c_to_k(C, DELTA) ((C) - (DELTA))
190 /* Do one forwards step in the "divide and conquer" graph traversal.
191 * left: the left side to diff.
192 * right: the right side to diff against.
193 * kd_forward: the traversal state for forwards traversal, modified by this
195 * This is carried over between invocations with increasing d.
196 * kd_forward points at the center of the state array, allowing
198 * kd_backward: the traversal state for backwards traversal, to find a meeting
200 * Since forwards is done first, kd_backward will be valid for d -
202 * kd_backward points at the center of the state array, allowing
204 * d: Step or distance counter, indicating for what value of d the kd_forward
205 * should be populated.
206 * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
208 * meeting_snake: resulting meeting point, if any.
209 * Return true when a meeting point has been identified.
212 diff_divide_myers_forward(bool *found_midpoint,
213 struct diff_data *left, struct diff_data *right,
214 int *kd_forward, int *kd_backward, int d,
215 struct diff_box *meeting_snake)
217 int delta = (int)right->atoms.len - (int)left->atoms.len;
223 *found_midpoint = false;
225 debug("-- %s d=%d\n", __func__, d);
227 for (k = d; k >= -d; k -= 2) {
228 if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
229 /* This diagonal is completely outside of the Myers
230 * graph, don't calculate it. */
231 if (k < -(int)right->atoms.len)
232 debug(" %d k < -(int)right->atoms.len %d\n", k,
233 -(int)right->atoms.len);
235 debug(" %d k > left->atoms.len %d\n", k,
238 /* We are traversing negatively, and already
239 * below the entire graph, nothing will come of
244 debug(" continue\n");
247 debug("- k = %d\n", k);
249 /* This is the initializing step. There is no prev_k
250 * yet, get the initial x from the top left of the Myers
254 prev_y = xk_to_y(x, k);
256 /* Favoring "-" lines first means favoring moving rightwards in
258 * For this, all k should derive from k - 1, only the bottom
259 * most k derive from k + 1:
262 * ----+----------------
264 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
270 * -1 | 0,1 <-- bottom most for d=1 from
271 * | \\ prev_k = -1 + 1 = 0
272 * -2 | 0,2 <-- bottom most for d=2 from
273 * prev_k = -2 + 1 = -1
275 * Except when a k + 1 from a previous run already means a
276 * further advancement in the graph.
277 * If k == d, there is no k + 1 and k - 1 is the only option.
278 * If k < d, use k + 1 in case that yields a larger x. Also use
279 * k + 1 if k - 1 is outside the graph.
283 || (k - 1 >= -(int)right->atoms.len
284 && kd_forward[k - 1] >= kd_forward[k + 1]))) {
285 /* Advance from k - 1.
286 * From position prev_k, step to the right in the Myers
290 prev_x = kd_forward[prev_k];
291 prev_y = xk_to_y(prev_x, prev_k);
294 /* The bottom most one.
295 * From position prev_k, step to the bottom in the Myers
297 * Incrementing y is achieved by decrementing k while
298 * keeping the same x.
299 * (since we're deriving y from y = x - k).
302 prev_x = kd_forward[prev_k];
303 prev_y = xk_to_y(prev_x, prev_k);
308 /* Slide down any snake that we might find here. */
309 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) {
311 int r = diff_atom_same(&same,
312 &left->atoms.head[x],
322 if (x_before_slide != x) {
323 debug(" down %d similar lines\n", x - x_before_slide);
329 for (fi = d; fi >= k; fi--) {
330 debug("kd_forward[%d] = (%d, %d)\n", fi,
331 kd_forward[fi], kd_forward[fi] - fi);
336 if (x < 0 || x > left->atoms.len
337 || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
340 /* Figured out a new forwards traversal, see if this has gone
341 * onto or even past a preceding backwards traversal.
343 * If the delta in length is odd, then d and backwards_d hit the
344 * same state indexes:
346 * ----+---------------- ----------------
356 * 0 | -->0,0 3,3====4,4 -1
363 * If the delta is even, they end up off-by-one, i.e. on
364 * different diagonals:
367 * ----+---------------- ----------------
375 * 0 | -->0,0 3,3 4,4<-- 0
382 * So in the forward path, we can only match up diagonals when
385 if ((delta & 1) == 0)
387 /* Forwards is done first, so the backwards one was still at
388 * d - 1. Can't do this for d == 0. */
389 int backwards_d = d - 1;
393 debug("backwards_d = %d\n", backwards_d);
395 /* If both sides have the same length, forward and backward
396 * start on the same diagonal, meaning the backwards state index
398 * As soon as the lengths are not the same, the backwards
399 * traversal starts on a different diagonal, and c = k shifted
400 * by the difference in length.
402 int c = k_to_c(k, delta);
404 /* When the file sizes are very different, the traversal trees
405 * start on far distant diagonals.
406 * They don't necessarily meet straight on. See whether this
407 * forward value is on a diagonal that is also valid in
408 * kd_backward[], and match them if so. */
409 if (c >= -backwards_d && c <= backwards_d) {
410 /* Current k is on a diagonal that exists in
411 * kd_backward[]. If the two x positions have met or
412 * passed (forward walked onto or past backward), then
413 * we've found a midpoint / a mid-box.
415 * When forwards and backwards traversals meet, the
416 * endpoints of the mid-snake are not the two points in
417 * kd_forward and kd_backward, but rather the section
418 * that was slid (if any) of the current
419 * forward/backward traversal only.
443 * The forward traversal reached M from the top and slid
444 * downwards to A. The backward traversal already
445 * reached X, which is not a straight line from M
446 * anymore, so picking a mid-snake from M to X would
449 * The correct mid-snake is between M and A. M is where
450 * the forward traversal hit the diagonal that the
451 * backward traversal has already passed, and A is what
452 * it reaches when sliding down identical lines.
454 int backward_x = kd_backward[c];
455 debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
456 k, c, x, xk_to_y(x, k), backward_x,
457 xc_to_y(backward_x, c, delta));
458 if (x >= backward_x) {
459 if (x_before_slide != x) {
460 /* met after sliding up a mid-snake */
461 *meeting_snake = (struct diff_box){
462 .left_start = x_before_slide,
464 .right_start = xc_to_y(x_before_slide,
466 .right_end = xk_to_y(x, k),
469 /* met after a side step, non-identical
470 * line. Mark that as box divider
471 * instead. This makes sure that
472 * myers_divide never returns the same
473 * box that came as input, avoiding
474 * "infinite" looping. */
475 *meeting_snake = (struct diff_box){
476 .left_start = prev_x,
478 .right_start = prev_y,
479 .right_end = xk_to_y(x, k),
482 debug("HIT x=(%u,%u) - y=(%u,%u)\n",
483 meeting_snake->left_start,
484 meeting_snake->right_start,
485 meeting_snake->left_end,
486 meeting_snake->right_end);
487 debug_dump_myers_graph(left, right, NULL,
490 *found_midpoint = true;
496 debug_dump_myers_graph(left, right, NULL, kd_forward, d,
501 /* Do one backwards step in the "divide and conquer" graph traversal.
502 * left: the left side to diff.
503 * right: the right side to diff against.
504 * kd_forward: the traversal state for forwards traversal, to find a meeting
506 * Since forwards is done first, after this, both kd_forward and
507 * kd_backward will be valid for d.
508 * kd_forward points at the center of the state array, allowing
510 * kd_backward: the traversal state for backwards traversal, to find a meeting
512 * This is carried over between invocations with increasing d.
513 * kd_backward points at the center of the state array, allowing
515 * d: Step or distance counter, indicating for what value of d the kd_backward
516 * should be populated.
517 * Before the first invocation, kd_backward[0] shall point at the bottom
518 * right of the Myers graph (left.len, right.len).
519 * The first invocation will be for d == 1.
520 * meeting_snake: resulting meeting point, if any.
521 * Return true when a meeting point has been identified.
524 diff_divide_myers_backward(bool *found_midpoint,
525 struct diff_data *left, struct diff_data *right,
526 int *kd_forward, int *kd_backward, int d,
527 struct diff_box *meeting_snake)
529 int delta = (int)right->atoms.len - (int)left->atoms.len;
536 *found_midpoint = false;
538 debug("-- %s d=%d\n", __func__, d);
540 for (c = d; c >= -d; c -= 2) {
541 if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
542 /* This diagonal is completely outside of the Myers
543 * graph, don't calculate it. */
544 if (c < -(int)left->atoms.len)
545 debug(" %d c < -(int)left->atoms.len %d\n", c,
546 -(int)left->atoms.len);
548 debug(" %d c > right->atoms.len %d\n", c,
551 /* We are traversing negatively, and already
552 * below the entire graph, nothing will come of
557 debug(" continue\n");
560 debug("- c = %d\n", c);
562 /* This is the initializing step. There is no prev_c
563 * yet, get the initial x from the bottom right of the
567 prev_y = xc_to_y(x, c, delta);
569 /* Favoring "-" lines first means favoring moving rightwards in
571 * For this, all c should derive from c - 1, only the bottom
572 * most c derive from c + 1:
575 * ---------------------------------------------------
579 * from prev_c = c - 1 --> 5,2 2
585 * bottom most for d=1 from c + 1 --> 4,4 -1
587 * bottom most for d=2 --> 3,4 -2
589 * Except when a c + 1 from a previous run already means a
590 * further advancement in the graph.
591 * If c == d, there is no c + 1 and c - 1 is the only option.
592 * If c < d, use c + 1 in case that yields a larger x.
593 * Also use c + 1 if c - 1 is outside the graph.
595 else if (c > -d && (c == d
596 || (c - 1 >= -(int)right->atoms.len
597 && kd_backward[c - 1] <= kd_backward[c + 1]))) {
599 * From position prev_c, step upwards in the Myers
601 * Decrementing y is achieved by incrementing c while
602 * keeping the same x. (since we're deriving y from
603 * y = x - c + delta).
606 prev_x = kd_backward[prev_c];
607 prev_y = xc_to_y(prev_x, prev_c, delta);
610 /* The bottom most one.
611 * From position prev_c, step to the left in the Myers
615 prev_x = kd_backward[prev_c];
616 prev_y = xc_to_y(prev_x, prev_c, delta);
620 /* Slide up any snake that we might find here (sections of
621 * identical lines on both sides). */
622 debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c,
624 xc_to_y(x, c, delta)-1);
627 debug_dump_atom(left, right, &left->atoms.head[x-1]);
629 if (xc_to_y(x, c, delta) > 0) {
631 debug_dump_atom(right, left,
632 &right->atoms.head[xc_to_y(x, c, delta)-1]);
635 while (x > 0 && xc_to_y(x, c, delta) > 0) {
637 int r = diff_atom_same(&same,
638 &left->atoms.head[x-1],
640 xc_to_y(x, c, delta)-1]);
648 if (x_before_slide != x) {
649 debug(" up %d similar lines\n", x_before_slide - x);
654 for (fi = d; fi >= c; fi--) {
655 debug("kd_backward[%d] = (%d, %d)\n",
658 kd_backward[fi] - fi + delta);
662 if (x < 0 || x > left->atoms.len
663 || xc_to_y(x, c, delta) < 0
664 || xc_to_y(x, c, delta) > right->atoms.len)
667 /* Figured out a new backwards traversal, see if this has gone
668 * onto or even past a preceding forwards traversal.
670 * If the delta in length is even, then d and backwards_d hit
671 * the same state indexes -- note how this is different from in
672 * the forwards traversal, because now both d are the same:
675 * ----+---------------- --------------------
685 * 0 | -->0,0 3,3====4,3 5,4<-- 0
692 * If the delta is odd, they end up off-by-one, i.e. on
693 * different diagonals.
694 * So in the backward path, we can only match up diagonals when
697 if ((delta & 1) != 0)
699 /* Forwards was done first, now both d are the same. */
702 /* As soon as the lengths are not the same, the
703 * backwards traversal starts on a different diagonal,
704 * and c = k shifted by the difference in length.
706 int k = c_to_k(c, delta);
708 /* When the file sizes are very different, the traversal trees
709 * start on far distant diagonals.
710 * They don't necessarily meet straight on. See whether this
711 * backward value is also on a valid diagonal in kd_forward[],
712 * and match them if so. */
713 if (k >= -forwards_d && k <= forwards_d) {
714 /* Current c is on a diagonal that exists in
715 * kd_forward[]. If the two x positions have met or
716 * passed (backward walked onto or past forward), then
717 * we've found a midpoint / a mid-box.
719 * When forwards and backwards traversals meet, the
720 * endpoints of the mid-snake are not the two points in
721 * kd_forward and kd_backward, but rather the section
722 * that was slid (if any) of the current
723 * forward/backward traversal only.
745 * The backward traversal reached M from the bottom and
746 * slid upwards. The forward traversal already reached
747 * X, which is not a straight line from M anymore, so
748 * picking a mid-snake from M to X would yield a
751 * The correct mid-snake is between M and A. M is where
752 * the backward traversal hit the diagonal that the
753 * forwards traversal has already passed, and A is what
754 * it reaches when sliding up identical lines.
757 int forward_x = kd_forward[k];
758 debug("Compare: k=%d c=%d is (%d,%d) >= (%d,%d)?\n",
759 k, c, forward_x, xk_to_y(forward_x, k),
760 x, xc_to_y(x, c, delta));
761 if (forward_x >= x) {
762 if (x_before_slide != x) {
763 /* met after sliding down a mid-snake */
764 *meeting_snake = (struct diff_box){
766 .left_end = x_before_slide,
767 .right_start = xc_to_y(x, c, delta),
768 .right_end = xk_to_y(x_before_slide, k),
771 /* met after a side step, non-identical
772 * line. Mark that as box divider
773 * instead. This makes sure that
774 * myers_divide never returns the same
775 * box that came as input, avoiding
776 * "infinite" looping. */
777 *meeting_snake = (struct diff_box){
780 .right_start = xc_to_y(x, c, delta),
784 debug("HIT x=%u,%u - y=%u,%u\n",
785 meeting_snake->left_start,
786 meeting_snake->right_start,
787 meeting_snake->left_end,
788 meeting_snake->right_end);
789 debug_dump_myers_graph(left, right, NULL,
792 *found_midpoint = true;
797 debug_dump_myers_graph(left, right, NULL, kd_forward, d, kd_backward,
802 /* Integer square root approximation */
807 for (i = 1; val > 0; val >>= 2)
812 /* Myers "Divide et Impera": tracing forwards from the start and backwards from
813 * the end to find a midpoint that divides the problem into smaller chunks.
814 * Requires only linear amounts of memory. */
816 diff_algo_myers_divide(const struct diff_algo_config *algo_config,
817 struct diff_state *state)
820 struct diff_data *left = &state->left;
821 struct diff_data *right = &state->right;
824 debug("\n** %s\n", __func__);
829 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
831 /* Allocate two columns of a Myers graph, one for the forward and one
832 * for the backward traversal. */
833 unsigned int max = left->atoms.len + right->atoms.len;
834 size_t kd_len = max + 1;
835 size_t kd_buf_size = kd_len << 1;
837 if (state->kd_buf_size < kd_buf_size) {
838 kd_buf = reallocarray(state->kd_buf, kd_buf_size,
842 state->kd_buf = kd_buf;
843 state->kd_buf_size = kd_buf_size;
845 kd_buf = state->kd_buf;
847 for (i = 0; i < kd_buf_size; i++)
849 int *kd_forward = kd_buf;
850 int *kd_backward = kd_buf + kd_len;
851 int max_effort = shift_sqrt(max/2);
853 /* The 'k' axis in Myers spans positive and negative indexes, so point
854 * the kd to the middle.
855 * It is then possible to index from -max/2 .. max/2. */
857 kd_backward += max/2;
860 struct diff_box mid_snake = {};
861 bool found_midpoint = false;
862 for (d = 0; d <= (max/2); d++) {
864 debug("-- d=%d\n", d);
865 r = diff_divide_myers_forward(&found_midpoint, left, right,
866 kd_forward, kd_backward, d,
872 r = diff_divide_myers_backward(&found_midpoint, left, right,
873 kd_forward, kd_backward, d,
880 /* Limit the effort spent looking for a mid snake. If files have
881 * very few lines in common, the effort spent to find nice mid
882 * snakes is just not worth it, the diff result will still be
883 * essentially minus everything on the left, plus everything on
884 * the right, with a few useless matches here and there. */
885 if (d > max_effort) {
886 /* pick the furthest reaching point from
887 * kd_forward and kd_backward, and use that as a
888 * midpoint, to not step into another diff algo
889 * recursion with unchanged box. */
890 int delta = (int)right->atoms.len - (int)left->atoms.len;
894 int best_forward_i = 0;
895 int best_forward_distance = 0;
896 int best_backward_i = 0;
897 int best_backward_distance = 0;
904 debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort);
905 debug_dump_myers_graph(left, right, NULL,
909 for (i = d; i >= -d; i -= 2) {
910 if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) {
914 if (distance > best_forward_distance) {
915 best_forward_distance = distance;
920 if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) {
922 y = xc_to_y(x, i, delta);
923 distance = (right->atoms.len - x)
924 + (left->atoms.len - y);
925 if (distance >= best_backward_distance) {
926 best_backward_distance = distance;
932 /* The myers-divide didn't meet in the middle. We just
933 * figured out the places where the forward path
934 * advanced the most, and the backward path advanced the
935 * most. Just divide at whichever one of those two is better.
955 best_forward_x = kd_forward[best_forward_i];
956 best_forward_y = xk_to_y(best_forward_x, best_forward_i);
957 best_backward_x = kd_backward[best_backward_i];
958 best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta);
960 if (best_forward_distance >= best_backward_distance) {
968 debug("max_effort cut at x=%d y=%d\n", x, y);
970 || x > left->atoms.len || y > right->atoms.len)
973 found_midpoint = true;
974 mid_snake = (struct diff_box){
984 if (!found_midpoint) {
985 /* Divide and conquer failed to find a meeting point. Use the
986 * fallback_algo defined in the algo_config (leave this to the
987 * caller). This is just paranoia/sanity, we normally should
988 * always find a midpoint.
990 debug(" no midpoint \n");
991 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
994 debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
995 mid_snake.left_start, mid_snake.left_end, left->atoms.len,
996 mid_snake.right_start, mid_snake.right_end,
999 /* Section before the mid-snake. */
1000 debug("Section before the mid-snake\n");
1002 struct diff_atom *left_atom = &left->atoms.head[0];
1003 unsigned int left_section_len = mid_snake.left_start;
1004 struct diff_atom *right_atom = &right->atoms.head[0];
1005 unsigned int right_section_len = mid_snake.right_start;
1007 if (left_section_len && right_section_len) {
1008 /* Record an unsolved chunk, the caller will apply
1009 * inner_algo() on this chunk. */
1010 if (!diff_state_add_chunk(state, false,
1011 left_atom, left_section_len,
1015 } else if (left_section_len && !right_section_len) {
1016 /* Only left atoms and none on the right, they form a
1017 * "minus" chunk, then. */
1018 if (!diff_state_add_chunk(state, true,
1019 left_atom, left_section_len,
1022 } else if (!left_section_len && right_section_len) {
1023 /* No left atoms, only atoms on the right, they form a
1024 * "plus" chunk, then. */
1025 if (!diff_state_add_chunk(state, true,
1031 /* else: left_section_len == 0 and right_section_len == 0, i.e.
1032 * nothing before the mid-snake. */
1034 if (mid_snake.left_end > mid_snake.left_start
1035 || mid_snake.right_end > mid_snake.right_start) {
1036 /* The midpoint is a section of identical data on both
1037 * sides, or a certain differing line: that section
1038 * immediately becomes a solved chunk. */
1039 debug("the mid-snake\n");
1040 if (!diff_state_add_chunk(state, true,
1041 &left->atoms.head[mid_snake.left_start],
1042 mid_snake.left_end - mid_snake.left_start,
1043 &right->atoms.head[mid_snake.right_start],
1044 mid_snake.right_end - mid_snake.right_start))
1048 /* Section after the mid-snake. */
1049 debug("Section after the mid-snake\n");
1050 debug(" left_end %u right_end %u\n",
1051 mid_snake.left_end, mid_snake.right_end);
1052 debug(" left_count %u right_count %u\n",
1053 left->atoms.len, right->atoms.len);
1054 left_atom = &left->atoms.head[mid_snake.left_end];
1055 left_section_len = left->atoms.len - mid_snake.left_end;
1056 right_atom = &right->atoms.head[mid_snake.right_end];
1057 right_section_len = right->atoms.len - mid_snake.right_end;
1059 if (left_section_len && right_section_len) {
1060 /* Record an unsolved chunk, the caller will apply
1061 * inner_algo() on this chunk. */
1062 if (!diff_state_add_chunk(state, false,
1063 left_atom, left_section_len,
1067 } else if (left_section_len && !right_section_len) {
1068 /* Only left atoms and none on the right, they form a
1069 * "minus" chunk, then. */
1070 if (!diff_state_add_chunk(state, true,
1071 left_atom, left_section_len,
1074 } else if (!left_section_len && right_section_len) {
1075 /* No left atoms, only atoms on the right, they form a
1076 * "plus" chunk, then. */
1077 if (!diff_state_add_chunk(state, true,
1083 /* else: left_section_len == 0 and right_section_len == 0, i.e.
1084 * nothing after the mid-snake. */
1090 debug("** END %s\n", __func__);
1094 /* Myers Diff tracing from the start all the way through to the end, requiring
1095 * quadratic amounts of memory. This can fail if the required space surpasses
1096 * algo_config->permitted_state_size. */
1098 diff_algo_myers(const struct diff_algo_config *algo_config,
1099 struct diff_state *state)
1101 /* do a diff_divide_myers_forward() without a _backward(), so that it
1102 * walks forward across the entire files to reach the end. Keep each
1103 * run's state, and do a final backtrace. */
1105 struct diff_data *left = &state->left;
1106 struct diff_data *right = &state->right;
1109 debug("\n** %s\n", __func__);
1114 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
1116 /* Allocate two columns of a Myers graph, one for the forward and one
1117 * for the backward traversal. */
1118 unsigned int max = left->atoms.len + right->atoms.len;
1119 size_t kd_len = max + 1 + max;
1120 size_t kd_buf_size = kd_len * kd_len;
1121 size_t kd_state_size = kd_buf_size * sizeof(int);
1122 debug("state size: %zu\n", kd_state_size);
1123 if (kd_buf_size < kd_len /* overflow? */
1124 || kd_state_size > algo_config->permitted_state_size) {
1125 debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
1126 kd_state_size, algo_config->permitted_state_size);
1127 return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1130 if (state->kd_buf_size < kd_buf_size) {
1131 kd_buf = reallocarray(state->kd_buf, kd_buf_size,
1135 state->kd_buf = kd_buf;
1136 state->kd_buf_size = kd_buf_size;
1138 kd_buf = state->kd_buf;
1141 for (i = 0; i < kd_buf_size; i++)
1144 /* The 'k' axis in Myers spans positive and negative indexes, so point
1145 * the kd to the middle.
1146 * It is then possible to index from -max .. max. */
1147 int *kd_origin = kd_buf + max;
1148 int *kd_column = kd_origin;
1151 int backtrack_d = -1;
1152 int backtrack_k = 0;
1155 for (d = 0; d <= max; d++, kd_column += kd_len) {
1156 debug("-- d=%d\n", d);
1158 debug("-- %s d=%d\n", __func__, d);
1160 for (k = d; k >= -d; k -= 2) {
1161 if (k < -(int)right->atoms.len
1162 || k > (int)left->atoms.len) {
1163 /* This diagonal is completely outside of the
1164 * Myers graph, don't calculate it. */
1165 if (k < -(int)right->atoms.len)
1167 " -(int)right->atoms.len %d\n",
1168 k, -(int)right->atoms.len);
1170 debug(" %d k > left->atoms.len %d\n", k,
1173 /* We are traversing negatively, and
1174 * already below the entire graph,
1175 * nothing will come of this. */
1179 debug(" continue\n");
1183 debug("- k = %d\n", k);
1185 /* This is the initializing step. There is no
1186 * prev_k yet, get the initial x from the top
1187 * left of the Myers graph. */
1190 int *kd_prev_column = kd_column - kd_len;
1192 /* Favoring "-" lines first means favoring
1193 * moving rightwards in the Myers graph.
1194 * For this, all k should derive from k - 1,
1195 * only the bottom most k derive from k + 1:
1198 * ----+----------------
1201 * | / prev_k = 2 - 1 = 1
1206 * -1 | 0,1 <-- bottom most for d=1
1207 * | \\ from prev_k = -1+1 = 0
1208 * -2 | 0,2 <-- bottom most for
1210 * prev_k = -2+1 = -1
1212 * Except when a k + 1 from a previous run
1213 * already means a further advancement in the
1215 * If k == d, there is no k + 1 and k - 1 is the
1217 * If k < d, use k + 1 in case that yields a
1218 * larger x. Also use k + 1 if k - 1 is outside
1223 || (k - 1 >= -(int)right->atoms.len
1224 && kd_prev_column[k - 1]
1225 >= kd_prev_column[k + 1]))) {
1226 /* Advance from k - 1.
1227 * From position prev_k, step to the
1228 * right in the Myers graph: x += 1.
1231 int prev_x = kd_prev_column[prev_k];
1234 /* The bottom most one.
1235 * From position prev_k, step to the
1236 * bottom in the Myers graph: y += 1.
1237 * Incrementing y is achieved by
1238 * decrementing k while keeping the same
1239 * x. (since we're deriving y from y =
1243 int prev_x = kd_prev_column[prev_k];
1248 /* Slide down any snake that we might find here. */
1249 while (x < left->atoms.len
1250 && xk_to_y(x, k) < right->atoms.len) {
1252 int r = diff_atom_same(&same,
1253 &left->atoms.head[x],
1266 for (fi = d; fi >= k; fi-=2) {
1267 debug("kd_column[%d] = (%d, %d)\n", fi,
1269 kd_column[fi] - fi);
1273 if (x == left->atoms.len
1274 && xk_to_y(x, k) == right->atoms.len) {
1278 debug("Reached the end at d = %d, k = %d\n",
1279 backtrack_d, backtrack_k);
1284 if (backtrack_d >= 0)
1288 debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
1290 /* backtrack. A matrix spanning from start to end of the file is ready:
1293 * ----+---------------------------------
1301 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
1308 * From (4,4) backwards, find the previous position that is the largest, and remember it.
1311 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
1315 /* When the best position is identified, remember it for that
1317 * That kd_column is no longer needed otherwise, so just
1318 * re-purpose kd_column[0] = x and kd_column[1] = y,
1319 * so that there is no need to allocate more memory.
1323 debug("Backtrack d=%d: xy=(%d, %d)\n",
1324 d, kd_column[0], kd_column[1]);
1326 /* Don't access memory before kd_buf */
1329 int *kd_prev_column = kd_column - kd_len;
1331 /* When y == 0, backtracking downwards (k-1) is the only way.
1332 * When x == 0, backtracking upwards (k+1) is the only way.
1335 * ----+---------------------------------
1343 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4,
1344 * | \ / \ backtrack_k = 0
1352 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1354 debug("prev k=k-1=%d x=%d y=%d\n",
1355 k, kd_prev_column[k],
1356 xk_to_y(kd_prev_column[k], k));
1359 debug("prev k=k+1=%d x=%d y=%d\n",
1360 k, kd_prev_column[k],
1361 xk_to_y(kd_prev_column[k], k));
1363 kd_column = kd_prev_column;
1366 /* Forwards again, this time recording the diff chunks.
1367 * Definitely start from 0,0. kd_column[0] may actually point to the
1368 * bottom of a snake starting at 0,0 */
1372 kd_column = kd_origin;
1373 for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1374 int next_x = kd_column[0];
1375 int next_y = kd_column[1];
1376 debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1377 x, y, next_x, next_y);
1379 struct diff_atom *left_atom = &left->atoms.head[x];
1380 int left_section_len = next_x - x;
1381 struct diff_atom *right_atom = &right->atoms.head[y];
1382 int right_section_len = next_y - y;
1385 if (left_section_len && right_section_len) {
1386 /* This must be a snake slide.
1387 * Snake slides have a straight line leading into them
1388 * (except when starting at (0,0)). Find out whether the
1389 * lead-in is horizontal or vertical:
1401 * If left_section_len > right_section_len, the lead-in
1402 * is horizontal, meaning first remove one atom from the
1403 * left before sliding down the snake.
1404 * If right_section_len > left_section_len, the lead-in
1405 * is vetical, so add one atom from the right before
1406 * sliding down the snake. */
1407 if (left_section_len == right_section_len + 1) {
1408 if (!diff_state_add_chunk(state, true,
1414 } else if (right_section_len == left_section_len + 1) {
1415 if (!diff_state_add_chunk(state, true,
1420 right_section_len--;
1421 } else if (left_section_len != right_section_len) {
1422 /* The numbers are making no sense. Should never
1424 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1428 if (!diff_state_add_chunk(state, true,
1429 left_atom, left_section_len,
1433 } else if (left_section_len && !right_section_len) {
1434 /* Only left atoms and none on the right, they form a
1435 * "minus" chunk, then. */
1436 if (!diff_state_add_chunk(state, true,
1437 left_atom, left_section_len,
1440 } else if (!left_section_len && right_section_len) {
1441 /* No left atoms, only atoms on the right, they form a
1442 * "plus" chunk, then. */
1443 if (!diff_state_add_chunk(state, true,
1457 debug("** END %s rc=%d\n", __func__, rc);