diff options
Diffstat (limited to 'lib/diff_myers.c')
| -rw-r--r-- | lib/diff_myers.c | 1425 |
1 files changed, 1425 insertions, 0 deletions
diff --git a/lib/diff_myers.c b/lib/diff_myers.c new file mode 100644 index 000000000000..c886d1a28586 --- /dev/null +++ b/lib/diff_myers.c @@ -0,0 +1,1425 @@ +/* Myers diff algorithm implementation, invented by Eugene W. Myers [1]. + * Implementations of both the Myers Divide Et Impera (using linear space) + * and the canonical Myers algorithm (using quadratic space). */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <errno.h> + +#include <arraylist.h> +#include <diff_main.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +/* Myers' diff algorithm [1] is nicely explained in [2]. + * [1] http://www.xmailserver.org/diff2.pdf + * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff. + * + * Myers approaches finding the smallest diff as a graph problem. + * The crux is that the original algorithm requires quadratic amount of memory: + * both sides' lengths added, and that squared. So if we're diffing lines of + * text, two files with 1000 lines each would blow up to a matrix of about + * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text. + * The solution is using Myers' "divide and conquer" extension algorithm, which + * does the original traversal from both ends of the files to reach a middle + * where these "snakes" touch, hence does not need to backtrace the traversal, + * and so gets away with only keeping a single column of that huge state matrix + * in memory. + */ + +struct diff_box { + unsigned int left_start; + unsigned int left_end; + unsigned int right_start; + unsigned int right_end; +}; + +/* If the two contents of a file are A B C D E and X B C Y, + * the Myers diff graph looks like: + * + * k0 k1 + * \ \ + * k-1 0 1 2 3 4 5 + * \ A B C D E + * 0 o-o-o-o-o-o + * X | | | | | | + * 1 o-o-o-o-o-o + * B | |\| | | | + * 2 o-o-o-o-o-o + * C | | |\| | | + * 3 o-o-o-o-o-o + * Y | | | | | |\ + * 4 o-o-o-o-o-o c1 + * \ \ + * c-1 c0 + * + * Moving right means delete an atom from the left-hand-side, + * Moving down means add an atom from the right-hand-side. + * Diagonals indicate identical atoms on both sides, the challenge is to use as + * many diagonals as possible. + * + * The original Myers algorithm walks all the way from the top left to the + * bottom right, remembers all steps, and then backtraces to find the shortest + * path. However, that requires keeping the entire graph in memory, which needs + * quadratic space. + * + * Myers adds a variant that uses linear space -- note, not linear time, only + * linear space: walk forward and backward, find a meeting point in the middle, + * and recurse on the two separate sections. This is called "divide and + * conquer". + * + * d: the step number, starting with 0, a.k.a. the distance from the starting + * point. + * k: relative index in the state array for the forward scan, indicating on + * which diagonal through the diff graph we currently are. + * c: relative index in the state array for the backward scan, indicating the + * diagonal number from the bottom up. + * + * The "divide and conquer" traversal through the Myers graph looks like this: + * + * | d= 0 1 2 3 2 1 0 + * ----+-------------------------------------------- + * k= | c= + * 4 | 3 + * | + * 3 | 3,0 5,2 2 + * | / \ + * 2 | 2,0 5,3 1 + * | / \ + * 1 | 1,0 4,3 >= 4,3 5,4<-- 0 + * | / / \ / + * 0 | -->0,0 3,3 4,4 -1 + * | \ / / + * -1 | 0,1 1,2 3,4 -2 + * | \ / + * -2 | 0,2 -3 + * | \ + * | 0,3 + * | forward-> <-backward + * + * x,y pairs here are the coordinates in the Myers graph: + * x = atom index in left-side source, y = atom index in the right-side source. + * + * Only one forward column and one backward column are kept in mem, each need at + * most left.len + 1 + right.len items. 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 + * odd items, the next column is formed in the even items, without overwriting + * the previous column's results. + * + * Also note that from the diagonal index k and the x coordinate, the y + * coordinate can be derived: + * y = x - k + * Hence the state array only needs to keep the x coordinate, i.e. the position + * in the left-hand file, and the y coordinate, i.e. position in the right-hand + * file, is derived from the index in the state array. + * + * The two traces meet at 4,3, the first step (here found in the forward + * traversal) where a forward position is on or past a backward traced position + * on the same diagonal. + * + * This divides the problem space into: + * + * 0 1 2 3 4 5 + * A B C D E + * 0 o-o-o-o-o + * X | | | | | + * 1 o-o-o-o-o + * B | |\| | | + * 2 o-o-o-o-o + * C | | |\| | + * 3 o-o-o-o-*-o *: forward and backward meet here + * Y | | + * 4 o-o + * + * Doing the same on each section lead to: + * + * 0 1 2 3 4 5 + * A B C D E + * 0 o-o + * X | | + * 1 o-b b: backward d=1 first reaches here (sliding up the snake) + * B \ f: then forward d=2 reaches here (sliding down the snake) + * 2 o As result, the box from b to f is found to be identical; + * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial + * 3 f-o tail 3,3 to 4,3. + * + * 3 o-* + * Y | + * 4 o *: forward and backward meet here + * + * and solving the last top left box gives: + * + * 0 1 2 3 4 5 + * A B C D E -A + * 0 o-o +X + * X | B + * 1 o C + * B \ -D + * 2 o -E + * C \ +Y + * 3 o-o-o + * Y | + * 4 o + * + */ + +#define xk_to_y(X, K) ((X) - (K)) +#define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA)) +#define k_to_c(K, DELTA) ((K) + (DELTA)) +#define c_to_k(C, DELTA) ((C) - (DELTA)) + +/* Do one forwards step in the "divide and conquer" graph traversal. + * left: the left side to diff. + * right: the right side to diff against. + * kd_forward: the traversal state for forwards traversal, modified by this + * function. + * This is carried over between invocations with increasing d. + * kd_forward points at the center of the state array, allowing + * negative indexes. + * kd_backward: the traversal state for backwards traversal, to find a meeting + * point. + * Since forwards is done first, kd_backward will be valid for d - + * 1, not d. + * kd_backward points at the center of the state array, allowing + * negative indexes. + * d: Step or distance counter, indicating for what value of d the kd_forward + * should be populated. + * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should + * be for d == 0. + * meeting_snake: resulting meeting point, if any. + * Return true when a meeting point has been identified. + */ +static int +diff_divide_myers_forward(bool *found_midpoint, + struct diff_data *left, struct diff_data *right, + int *kd_forward, int *kd_backward, int d, + struct diff_box *meeting_snake) +{ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int k; + int x; + int prev_x; + int prev_y; + int x_before_slide; + *found_midpoint = false; + + for (k = d; k >= -d; k -= 2) { + if (k < -(int)right->atoms.len || k > (int)left->atoms.len) { + /* This diagonal is completely outside of the Myers + * graph, don't calculate it. */ + if (k < 0) { + /* We are traversing negatively, and already + * below the entire graph, nothing will come of + * this. */ + debug(" break\n"); + break; + } + debug(" continue\n"); + continue; + } + if (d == 0) { + /* This is the initializing step. There is no prev_k + * yet, get the initial x from the top left of the Myers + * graph. */ + x = 0; + prev_x = x; + prev_y = xk_to_y(x, k); + } + /* Favoring "-" lines first means favoring moving rightwards in + * the Myers graph. + * For this, all k should derive from k - 1, only the bottom + * most k derive from k + 1: + * + * | d= 0 1 2 + * ----+---------------- + * k= | + * 2 | 2,0 <-- from prev_k = 2 - 1 = 1 + * | / + * 1 | 1,0 + * | / + * 0 | -->0,0 3,3 + * | \\ / + * -1 | 0,1 <-- bottom most for d=1 from + * | \\ prev_k = -1 + 1 = 0 + * -2 | 0,2 <-- bottom most for d=2 from + * prev_k = -2 + 1 = -1 + * + * Except when a k + 1 from a previous run already means a + * further advancement in the graph. + * If k == d, there is no k + 1 and k - 1 is the only option. + * If k < d, use k + 1 in case that yields a larger x. Also use + * k + 1 if k - 1 is outside the graph. + */ + else if (k > -d + && (k == d + || (k - 1 >= -(int)right->atoms.len + && kd_forward[k - 1] >= kd_forward[k + 1]))) { + /* Advance from k - 1. + * From position prev_k, step to the right in the Myers + * graph: x += 1. + */ + int prev_k = k - 1; + prev_x = kd_forward[prev_k]; + prev_y = xk_to_y(prev_x, prev_k); + x = prev_x + 1; + } else { + /* The bottom most one. + * From position prev_k, step to the bottom in the Myers + * graph: y += 1. + * Incrementing y is achieved by decrementing k while + * keeping the same x. + * (since we're deriving y from y = x - k). + */ + int prev_k = k + 1; + prev_x = kd_forward[prev_k]; + prev_y = xk_to_y(prev_x, prev_k); + x = prev_x; + } + + x_before_slide = x; + /* Slide down any snake that we might find here. */ + while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x], + &right->atoms.head[ + xk_to_y(x, k)]); + if (r) + return r; + if (!same) + break; + x++; + } + kd_forward[k] = x; +#if 0 + if (x_before_slide != x) { + debug(" down %d similar lines\n", x - x_before_slide); + } + +#if DEBUG + { + int fi; + for (fi = d; fi >= k; fi--) { + debug("kd_forward[%d] = (%d, %d)\n", fi, + kd_forward[fi], kd_forward[fi] - fi); + } + } +#endif +#endif + + if (x < 0 || x > left->atoms.len + || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) + continue; + + /* Figured out a new forwards traversal, see if this has gone + * onto or even past a preceding backwards traversal. + * + * If the delta in length is odd, then d and backwards_d hit the + * same state indexes: + * | d= 0 1 2 1 0 + * ----+---------------- ---------------- + * k= | c= + * 4 | 3 + * | + * 3 | 2 + * | same + * 2 | 2,0====5,3 1 + * | / \ + * 1 | 1,0 5,4<-- 0 + * | / / + * 0 | -->0,0 3,3====4,4 -1 + * | \ / + * -1 | 0,1 -2 + * | \ + * -2 | 0,2 -3 + * | + * + * If the delta is even, they end up off-by-one, i.e. on + * different diagonals: + * + * | d= 0 1 2 1 0 + * ----+---------------- ---------------- + * | c= + * 3 | 3 + * | + * 2 | 2,0 off 2 + * | / \\ + * 1 | 1,0 4,3 1 + * | / // \ + * 0 | -->0,0 3,3 4,4<-- 0 + * | \ / / + * -1 | 0,1 3,4 -1 + * | \ // + * -2 | 0,2 -2 + * | + * + * So in the forward path, we can only match up diagonals when + * the delta is odd. + */ + if ((delta & 1) == 0) + continue; + /* Forwards is done first, so the backwards one was still at + * d - 1. Can't do this for d == 0. */ + int backwards_d = d - 1; + if (backwards_d < 0) + continue; + + /* If both sides have the same length, forward and backward + * start on the same diagonal, meaning the backwards state index + * c == k. + * As soon as the lengths are not the same, the backwards + * traversal starts on a different diagonal, and c = k shifted + * by the difference in length. + */ + int c = k_to_c(k, delta); + + /* When the file sizes are very different, the traversal trees + * start on far distant diagonals. + * They don't necessarily meet straight on. See whether this + * forward value is on a diagonal that is also valid in + * kd_backward[], and match them if so. */ + if (c >= -backwards_d && c <= backwards_d) { + /* Current k is on a diagonal that exists in + * kd_backward[]. If the two x positions have met or + * passed (forward walked onto or past backward), then + * we've found a midpoint / a mid-box. + * + * When forwards and backwards traversals meet, the + * endpoints of the mid-snake are not the two points in + * kd_forward and kd_backward, but rather the section + * that was slid (if any) of the current + * forward/backward traversal only. + * + * For example: + * + * o + * \ + * o + * \ + * o + * \ + * o + * \ + * X o o + * | | | + * o-o-o o + * \| + * M + * \ + * o + * \ + * A o + * | | + * o-o-o + * + * The forward traversal reached M from the top and slid + * downwards to A. The backward traversal already + * reached X, which is not a straight line from M + * anymore, so picking a mid-snake from M to X would + * yield a mistake. + * + * The correct mid-snake is between M and A. M is where + * the forward traversal hit the diagonal that the + * backward traversal has already passed, and A is what + * it reaches when sliding down identical lines. + */ + int backward_x = kd_backward[c]; + if (x >= backward_x) { + if (x_before_slide != x) { + /* met after sliding up a mid-snake */ + *meeting_snake = (struct diff_box){ + .left_start = x_before_slide, + .left_end = x, + .right_start = xc_to_y(x_before_slide, + c, delta), + .right_end = xk_to_y(x, k), + }; + } else { + /* met after a side step, non-identical + * line. Mark that as box divider + * instead. This makes sure that + * myers_divide never returns the same + * box that came as input, avoiding + * "infinite" looping. */ + *meeting_snake = (struct diff_box){ + .left_start = prev_x, + .left_end = x, + .right_start = prev_y, + .right_end = xk_to_y(x, k), + }; + } + debug("HIT x=(%u,%u) - y=(%u,%u)\n", + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d-1); + *found_midpoint = true; + return 0; + } + } + } + + return 0; +} + +/* Do one backwards step in the "divide and conquer" graph traversal. + * left: the left side to diff. + * right: the right side to diff against. + * kd_forward: the traversal state for forwards traversal, to find a meeting + * point. + * Since forwards is done first, after this, both kd_forward and + * kd_backward will be valid for d. + * kd_forward points at the center of the state array, allowing + * negative indexes. + * kd_backward: the traversal state for backwards traversal, to find a meeting + * point. + * This is carried over between invocations with increasing d. + * kd_backward points at the center of the state array, allowing + * negative indexes. + * d: Step or distance counter, indicating for what value of d the kd_backward + * should be populated. + * Before the first invocation, kd_backward[0] shall point at the bottom + * right of the Myers graph (left.len, right.len). + * The first invocation will be for d == 1. + * meeting_snake: resulting meeting point, if any. + * Return true when a meeting point has been identified. + */ +static int +diff_divide_myers_backward(bool *found_midpoint, + struct diff_data *left, struct diff_data *right, + int *kd_forward, int *kd_backward, int d, + struct diff_box *meeting_snake) +{ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int c; + int x; + int prev_x; + int prev_y; + int x_before_slide; + + *found_midpoint = false; + + for (c = d; c >= -d; c -= 2) { + if (c < -(int)left->atoms.len || c > (int)right->atoms.len) { + /* This diagonal is completely outside of the Myers + * graph, don't calculate it. */ + if (c < 0) { + /* We are traversing negatively, and already + * below the entire graph, nothing will come of + * this. */ + break; + } + continue; + } + if (d == 0) { + /* This is the initializing step. There is no prev_c + * yet, get the initial x from the bottom right of the + * Myers graph. */ + x = left->atoms.len; + prev_x = x; + prev_y = xc_to_y(x, c, delta); + } + /* Favoring "-" lines first means favoring moving rightwards in + * the Myers graph. + * For this, all c should derive from c - 1, only the bottom + * most c derive from c + 1: + * + * 2 1 0 + * --------------------------------------------------- + * c= + * 3 + * + * from prev_c = c - 1 --> 5,2 2 + * \ + * 5,3 1 + * \ + * 4,3 5,4<-- 0 + * \ / + * bottom most for d=1 from c + 1 --> 4,4 -1 + * / + * bottom most for d=2 --> 3,4 -2 + * + * Except when a c + 1 from a previous run already means a + * further advancement in the graph. + * If c == d, there is no c + 1 and c - 1 is the only option. + * If c < d, use c + 1 in case that yields a larger x. + * Also use c + 1 if c - 1 is outside the graph. + */ + else if (c > -d && (c == d + || (c - 1 >= -(int)right->atoms.len + && kd_backward[c - 1] <= kd_backward[c + 1]))) { + /* A top one. + * From position prev_c, step upwards in the Myers + * graph: y -= 1. + * Decrementing y is achieved by incrementing c while + * keeping the same x. (since we're deriving y from + * y = x - c + delta). + */ + int prev_c = c - 1; + prev_x = kd_backward[prev_c]; + prev_y = xc_to_y(prev_x, prev_c, delta); + x = prev_x; + } else { + /* The bottom most one. + * From position prev_c, step to the left in the Myers + * graph: x -= 1. + */ + int prev_c = c + 1; + prev_x = kd_backward[prev_c]; + prev_y = xc_to_y(prev_x, prev_c, delta); + x = prev_x - 1; + } + + /* Slide up any snake that we might find here (sections of + * identical lines on both sides). */ +#if 0 + 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); + if (x > 0) { + debug(" l="); + debug_dump_atom(left, right, &left->atoms.head[x-1]); + } + if (xc_to_y(x, c, delta) > 0) { + debug(" r="); + debug_dump_atom(right, left, + &right->atoms.head[xc_to_y(x, c, delta)-1]); + } +#endif + x_before_slide = x; + while (x > 0 && xc_to_y(x, c, delta) > 0) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x-1], + &right->atoms.head[ + xc_to_y(x, c, delta)-1]); + if (r) + return r; + if (!same) + break; + x--; + } + kd_backward[c] = x; +#if 0 + if (x_before_slide != x) { + debug(" up %d similar lines\n", x_before_slide - x); + } + + if (DEBUG) { + int fi; + for (fi = d; fi >= c; fi--) { + debug("kd_backward[%d] = (%d, %d)\n", + fi, + kd_backward[fi], + kd_backward[fi] - fi + delta); + } + } +#endif + + if (x < 0 || x > left->atoms.len + || xc_to_y(x, c, delta) < 0 + || xc_to_y(x, c, delta) > right->atoms.len) + continue; + + /* Figured out a new backwards traversal, see if this has gone + * onto or even past a preceding forwards traversal. + * + * If the delta in length is even, then d and backwards_d hit + * the same state indexes -- note how this is different from in + * the forwards traversal, because now both d are the same: + * + * | d= 0 1 2 2 1 0 + * ----+---------------- -------------------- + * k= | c= + * 4 | + * | + * 3 | 3 + * | same + * 2 | 2,0====5,2 2 + * | / \ + * 1 | 1,0 5,3 1 + * | / / \ + * 0 | -->0,0 3,3====4,3 5,4<-- 0 + * | \ / / + * -1 | 0,1 4,4 -1 + * | \ + * -2 | 0,2 -2 + * | + * -3 + * If the delta is odd, they end up off-by-one, i.e. on + * different diagonals. + * So in the backward path, we can only match up diagonals when + * the delta is even. + */ + if ((delta & 1) != 0) + continue; + /* Forwards was done first, now both d are the same. */ + int forwards_d = d; + + /* As soon as the lengths are not the same, the + * backwards traversal starts on a different diagonal, + * and c = k shifted by the difference in length. + */ + int k = c_to_k(c, delta); + + /* When the file sizes are very different, the traversal trees + * start on far distant diagonals. + * They don't necessarily meet straight on. See whether this + * backward value is also on a valid diagonal in kd_forward[], + * and match them if so. */ + if (k >= -forwards_d && k <= forwards_d) { + /* Current c is on a diagonal that exists in + * kd_forward[]. If the two x positions have met or + * passed (backward walked onto or past forward), then + * we've found a midpoint / a mid-box. + * + * When forwards and backwards traversals meet, the + * endpoints of the mid-snake are not the two points in + * kd_forward and kd_backward, but rather the section + * that was slid (if any) of the current + * forward/backward traversal only. + * + * For example: + * + * o-o-o + * | | + * o A + * | \ + * o o + * \ + * M + * |\ + * o o-o-o + * | | | + * o o X + * \ + * o + * \ + * o + * \ + * o + * + * The backward traversal reached M from the bottom and + * slid upwards. The forward traversal already reached + * X, which is not a straight line from M anymore, so + * picking a mid-snake from M to X would yield a + * mistake. + * + * The correct mid-snake is between M and A. M is where + * the backward traversal hit the diagonal that the + * forwards traversal has already passed, and A is what + * it reaches when sliding up identical lines. + */ + + int forward_x = kd_forward[k]; + if (forward_x >= x) { + if (x_before_slide != x) { + /* met after sliding down a mid-snake */ + *meeting_snake = (struct diff_box){ + .left_start = x, + .left_end = x_before_slide, + .right_start = xc_to_y(x, c, delta), + .right_end = xk_to_y(x_before_slide, k), + }; + } else { + /* met after a side step, non-identical + * line. Mark that as box divider + * instead. This makes sure that + * myers_divide never returns the same + * box that came as input, avoiding + * "infinite" looping. */ + *meeting_snake = (struct diff_box){ + .left_start = x, + .left_end = prev_x, + .right_start = xc_to_y(x, c, delta), + .right_end = prev_y, + }; + } + debug("HIT x=%u,%u - y=%u,%u\n", + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d); + *found_midpoint = true; + return 0; + } + } + } + return 0; +} + +/* Integer square root approximation */ +static int +shift_sqrt(int val) +{ + int i; + for (i = 1; val > 0; val >>= 2) + i <<= 1; + return i; +} + +#define DIFF_EFFORT_MIN 1024 + +/* Myers "Divide et Impera": tracing forwards from the start and backwards from + * the end to find a midpoint that divides the problem into smaller chunks. + * Requires only linear amounts of memory. */ +int +diff_algo_myers_divide(const struct diff_algo_config *algo_config, + struct diff_state *state) +{ + int rc = ENOMEM; + struct diff_data *left = &state->left; + struct diff_data *right = &state->right; + int *kd_buf; + + debug("\n** %s\n", __func__); + debug("left:\n"); + debug_dump(left); + debug("right:\n"); + debug_dump(right); + + /* Allocate two columns of a Myers graph, one for the forward and one + * for the backward traversal. */ + unsigned int max = left->atoms.len + right->atoms.len; + size_t kd_len = max + 1; + size_t kd_buf_size = kd_len << 1; + + if (state->kd_buf_size < kd_buf_size) { + kd_buf = reallocarray(state->kd_buf, kd_buf_size, + sizeof(int)); + if (!kd_buf) + return ENOMEM; + state->kd_buf = kd_buf; + state->kd_buf_size = kd_buf_size; + } else + kd_buf = state->kd_buf; + int i; + for (i = 0; i < kd_buf_size; i++) + kd_buf[i] = -1; + int *kd_forward = kd_buf; + int *kd_backward = kd_buf + kd_len; + int max_effort = shift_sqrt(max/2); + + if (max_effort < DIFF_EFFORT_MIN) + max_effort = DIFF_EFFORT_MIN; + + /* The 'k' axis in Myers spans positive and negative indexes, so point + * the kd to the middle. + * It is then possible to index from -max/2 .. max/2. */ + kd_forward += max/2; + kd_backward += max/2; + + int d; + struct diff_box mid_snake = {}; + bool found_midpoint = false; + for (d = 0; d <= (max/2); d++) { + int r; + r = diff_divide_myers_forward(&found_midpoint, left, right, + kd_forward, kd_backward, d, + &mid_snake); + if (r) + return r; + if (found_midpoint) + break; + r = diff_divide_myers_backward(&found_midpoint, left, right, + kd_forward, kd_backward, d, + &mid_snake); + if (r) + return r; + if (found_midpoint) + break; + + /* Limit the effort spent looking for a mid snake. If files have + * very few lines in common, the effort spent to find nice mid + * snakes is just not worth it, the diff result will still be + * essentially minus everything on the left, plus everything on + * the right, with a few useless matches here and there. */ + if (d > max_effort) { + /* pick the furthest reaching point from + * kd_forward and kd_backward, and use that as a + * midpoint, to not step into another diff algo + * recursion with unchanged box. */ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int x = 0; + int y; + int i; + int best_forward_i = 0; + int best_forward_distance = 0; + int best_backward_i = 0; + int best_backward_distance = 0; + int distance; + int best_forward_x; + int best_forward_y; + int best_backward_x; + int best_backward_y; + + debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d); + + for (i = d; i >= -d; i -= 2) { + if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) { + x = kd_forward[i]; + y = xk_to_y(x, i); + distance = x + y; + if (distance > best_forward_distance) { + best_forward_distance = distance; + best_forward_i = i; + } + } + + if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) { + x = kd_backward[i]; + y = xc_to_y(x, i, delta); + distance = (right->atoms.len - x) + + (left->atoms.len - y); + if (distance >= best_backward_distance) { + best_backward_distance = distance; + best_backward_i = i; + } + } + } + + /* The myers-divide didn't meet in the middle. We just + * figured out the places where the forward path + * advanced the most, and the backward path advanced the + * most. Just divide at whichever one of those two is better. + * + * o-o + * | + * o + * \ + * o + * \ + * F <-- cut here + * + * + * + * or here --> B + * \ + * o + * \ + * o + * | + * o-o + */ + best_forward_x = kd_forward[best_forward_i]; + best_forward_y = xk_to_y(best_forward_x, best_forward_i); + best_backward_x = kd_backward[best_backward_i]; + best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta); + + if (best_forward_distance >= best_backward_distance) { + x = best_forward_x; + y = best_forward_y; + } else { + x = best_backward_x; + y = best_backward_y; + } + + debug("max_effort cut at x=%d y=%d\n", x, y); + if (x < 0 || y < 0 + || x > left->atoms.len || y > right->atoms.len) + break; + + found_midpoint = true; + mid_snake = (struct diff_box){ + .left_start = x, + .left_end = x, + .right_start = y, + .right_end = y, + }; + break; + } + } + + if (!found_midpoint) { + /* Divide and conquer failed to find a meeting point. Use the + * fallback_algo defined in the algo_config (leave this to the + * caller). This is just paranoia/sanity, we normally should + * always find a midpoint. + */ + debug(" no midpoint \n"); + rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK; + goto return_rc; + } else { + debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n", + mid_snake.left_start, mid_snake.left_end, left->atoms.len, + mid_snake.right_start, mid_snake.right_end, + right->atoms.len); + + /* Section before the mid-snake. */ + debug("Section before the mid-snake\n"); + + struct diff_atom *left_atom = &left->atoms.head[0]; + unsigned int left_section_len = mid_snake.left_start; + struct diff_atom *right_atom = &right->atoms.head[0]; + unsigned int right_section_len = mid_snake.right_start; + + if (left_section_len && right_section_len) { + /* Record an unsolved chunk, the caller will apply + * inner_algo() on this chunk. */ + if (!diff_state_add_chunk(state, false, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + /* else: left_section_len == 0 and right_section_len == 0, i.e. + * nothing before the mid-snake. */ + + if (mid_snake.left_end > mid_snake.left_start + || mid_snake.right_end > mid_snake.right_start) { + /* The midpoint is a section of identical data on both + * sides, or a certain differing line: that section + * immediately becomes a solved chunk. */ + debug("the mid-snake\n"); + if (!diff_state_add_chunk(state, true, + &left->atoms.head[mid_snake.left_start], + mid_snake.left_end - mid_snake.left_start, + &right->atoms.head[mid_snake.right_start], + mid_snake.right_end - mid_snake.right_start)) + goto return_rc; + } + + /* Section after the mid-snake. */ + debug("Section after the mid-snake\n"); + debug(" left_end %u right_end %u\n", + mid_snake.left_end, mid_snake.right_end); + debug(" left_count %u right_count %u\n", + left->atoms.len, right->atoms.len); + left_atom = &left->atoms.head[mid_snake.left_end]; + left_section_len = left->atoms.len - mid_snake.left_end; + right_atom = &right->atoms.head[mid_snake.right_end]; + right_section_len = right->atoms.len - mid_snake.right_end; + + if (left_section_len && right_section_len) { + /* Record an unsolved chunk, the caller will apply + * inner_algo() on this chunk. */ + if (!diff_state_add_chunk(state, false, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + /* else: left_section_len == 0 and right_section_len == 0, i.e. + * nothing after the mid-snake. */ + } + + rc = DIFF_RC_OK; + +return_rc: + debug("** END %s\n", __func__); + return rc; +} + +/* Myers Diff tracing from the start all the way through to the end, requiring + * quadratic amounts of memory. This can fail if the required space surpasses + * algo_config->permitted_state_size. */ +int +diff_algo_myers(const struct diff_algo_config *algo_config, + struct diff_state *state) +{ + /* do a diff_divide_myers_forward() without a _backward(), so that it + * walks forward across the entire files to reach the end. Keep each + * run's state, and do a final backtrace. */ + int rc = ENOMEM; + struct diff_data *left = &state->left; + struct diff_data *right = &state->right; + int *kd_buf; + + debug("\n** %s\n", __func__); + debug("left:\n"); + debug_dump(left); + debug("right:\n"); + debug_dump(right); + debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0); + + /* Allocate two columns of a Myers graph, one for the forward and one + * for the backward traversal. */ + unsigned int max = left->atoms.len + right->atoms.len; + size_t kd_len = max + 1 + max; + size_t kd_buf_size = kd_len * kd_len; + size_t kd_state_size = kd_buf_size * sizeof(int); + debug("state size: %zu\n", kd_state_size); + if (kd_buf_size < kd_len /* overflow? */ + || (SIZE_MAX / kd_len ) < kd_len + || kd_state_size > algo_config->permitted_state_size) { + debug("state size %zu > permitted_state_size %zu, use fallback_algo\n", + kd_state_size, algo_config->permitted_state_size); + return DIFF_RC_USE_DIFF_ALGO_FALLBACK; + } + + if (state->kd_buf_size < kd_buf_size) { + kd_buf = reallocarray(state->kd_buf, kd_buf_size, + sizeof(int)); + if (!kd_buf) + return ENOMEM; + state->kd_buf = kd_buf; + state->kd_buf_size = kd_buf_size; + } else + kd_buf = state->kd_buf; + + int i; + for (i = 0; i < kd_buf_size; i++) + kd_buf[i] = -1; + + /* The 'k' axis in Myers spans positive and negative indexes, so point + * the kd to the middle. + * It is then possible to index from -max .. max. */ + int *kd_origin = kd_buf + max; + int *kd_column = kd_origin; + + int d; + int backtrack_d = -1; + int backtrack_k = 0; + int k; + int x, y; + for (d = 0; d <= max; d++, kd_column += kd_len) { + debug("-- %s d=%d\n", __func__, d); + + for (k = d; k >= -d; k -= 2) { + if (k < -(int)right->atoms.len + || k > (int)left->atoms.len) { + /* This diagonal is completely outside of the + * Myers graph, don't calculate it. */ + if (k < -(int)right->atoms.len) + debug(" %d k <" + " -(int)right->atoms.len %d\n", + k, -(int)right->atoms.len); + else + debug(" %d k > left->atoms.len %d\n", k, + left->atoms.len); + if (k < 0) { + /* We are traversing negatively, and + * already below the entire graph, + * nothing will come of this. */ + debug(" break\n"); + break; + } + debug(" continue\n"); + continue; + } + + if (d == 0) { + /* This is the initializing step. There is no + * prev_k yet, get the initial x from the top + * left of the Myers graph. */ + x = 0; + } else { + int *kd_prev_column = kd_column - kd_len; + + /* Favoring "-" lines first means favoring + * moving rightwards in the Myers graph. + * For this, all k should derive from k - 1, + * only the bottom most k derive from k + 1: + * + * | d= 0 1 2 + * ----+---------------- + * k= | + * 2 | 2,0 <-- from + * | / prev_k = 2 - 1 = 1 + * 1 | 1,0 + * | / + * 0 | -->0,0 3,3 + * | \\ / + * -1 | 0,1 <-- bottom most for d=1 + * | \\ from prev_k = -1+1 = 0 + * -2 | 0,2 <-- bottom most for + * d=2 from + * prev_k = -2+1 = -1 + * + * Except when a k + 1 from a previous run + * already means a further advancement in the + * graph. + * If k == d, there is no k + 1 and k - 1 is the + * only option. + * If k < d, use k + 1 in case that yields a + * larger x. Also use k + 1 if k - 1 is outside + * the graph. + */ + if (k > -d + && (k == d + || (k - 1 >= -(int)right->atoms.len + && kd_prev_column[k - 1] + >= kd_prev_column[k + 1]))) { + /* Advance from k - 1. + * From position prev_k, step to the + * right in the Myers graph: x += 1. + */ + int prev_k = k - 1; + int prev_x = kd_prev_column[prev_k]; + x = prev_x + 1; + } else { + /* The bottom most one. + * From position prev_k, step to the + * bottom in the Myers graph: y += 1. + * Incrementing y is achieved by + * decrementing k while keeping the same + * x. (since we're deriving y from y = + * x - k). + */ + int prev_k = k + 1; + int prev_x = kd_prev_column[prev_k]; + x = prev_x; + } + } + + /* Slide down any snake that we might find here. */ + while (x < left->atoms.len + && xk_to_y(x, k) < right->atoms.len) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x], + &right->atoms.head[ + xk_to_y(x, k)]); + if (r) + return r; + if (!same) + break; + x++; + } + kd_column[k] = x; + + if (x == left->atoms.len + && xk_to_y(x, k) == right->atoms.len) { + /* Found a path */ + backtrack_d = d; + backtrack_k = k; + debug("Reached the end at d = %d, k = %d\n", + backtrack_d, backtrack_k); + break; + } + } + + if (backtrack_d >= 0) + break; + } + + debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0); + + /* backtrack. A matrix spanning from start to end of the file is ready: + * + * | d= 0 1 2 3 4 + * ----+--------------------------------- + * k= | + * 3 | + * | + * 2 | 2,0 + * | / + * 1 | 1,0 4,3 + * | / / \ + * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0 + * | \ / \ + * -1 | 0,1 3,4 + * | \ + * -2 | 0,2 + * | + * + * From (4,4) backwards, find the previous position that is the largest, and remember it. + * + */ + for (d = backtrack_d, k = backtrack_k; d >= 0; d--) { + x = kd_column[k]; + y = xk_to_y(x, k); + + /* When the best position is identified, remember it for that + * kd_column. + * That kd_column is no longer needed otherwise, so just + * re-purpose kd_column[0] = x and kd_column[1] = y, + * so that there is no need to allocate more memory. + */ + kd_column[0] = x; + kd_column[1] = y; + debug("Backtrack d=%d: xy=(%d, %d)\n", + d, kd_column[0], kd_column[1]); + + /* Don't access memory before kd_buf */ + if (d == 0) + break; + int *kd_prev_column = kd_column - kd_len; + + /* When y == 0, backtracking downwards (k-1) is the only way. + * When x == 0, backtracking upwards (k+1) is the only way. + * + * | d= 0 1 2 3 4 + * ----+--------------------------------- + * k= | + * 3 | + * | ..y == 0 + * 2 | 2,0 + * | / + * 1 | 1,0 4,3 + * | / / \ + * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, + * | \ / \ backtrack_k = 0 + * -1 | 0,1 3,4 + * | \ + * -2 | 0,2__ + * | x == 0 + */ + if (y == 0 + || (x > 0 + && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { + k = k - 1; + debug("prev k=k-1=%d x=%d y=%d\n", + k, kd_prev_column[k], + xk_to_y(kd_prev_column[k], k)); + } else { + k = k + 1; + debug("prev k=k+1=%d x=%d y=%d\n", + k, kd_prev_column[k], + xk_to_y(kd_prev_column[k], k)); + } + kd_column = kd_prev_column; + } + + /* Forwards again, this time recording the diff chunks. + * Definitely start from 0,0. kd_column[0] may actually point to the + * bottom of a snake starting at 0,0 */ + x = 0; + y = 0; + + kd_column = kd_origin; + for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) { + int next_x = kd_column[0]; + int next_y = kd_column[1]; + debug("Forward track from xy(%d,%d) to xy(%d,%d)\n", + x, y, next_x, next_y); + + struct diff_atom *left_atom = &left->atoms.head[x]; + int left_section_len = next_x - x; + struct diff_atom *right_atom = &right->atoms.head[y]; + int right_section_len = next_y - y; + + rc = ENOMEM; + if (left_section_len && right_section_len) { + /* This must be a snake slide. + * Snake slides have a straight line leading into them + * (except when starting at (0,0)). Find out whether the + * lead-in is horizontal or vertical: + * + * left + * ----------> + * | + * r| o-o o + * i| \ | + * g| o o + * h| \ \ + * t| o o + * v + * + * If left_section_len > right_section_len, the lead-in + * is horizontal, meaning first remove one atom from the + * left before sliding down the snake. + * If right_section_len > left_section_len, the lead-in + * is vetical, so add one atom from the right before + * sliding down the snake. */ + if (left_section_len == right_section_len + 1) { + if (!diff_state_add_chunk(state, true, + left_atom, 1, + right_atom, 0)) + goto return_rc; + left_atom++; + left_section_len--; + } else if (right_section_len == left_section_len + 1) { + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, 1)) + goto return_rc; + right_atom++; + right_section_len--; + } else if (left_section_len != right_section_len) { + /* The numbers are making no sense. Should never + * happen. */ + rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK; + goto return_rc; + } + + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + + x = next_x; + y = next_y; + } + + rc = DIFF_RC_OK; + +return_rc: + debug("** END %s rc=%d\n", __func__, rc); + return rc; +} |