thodg/got/lib/diff_myers.c

• Show log

  Commit

• Hash : f6f4c787
  Author :
  Date : 2021-11-23T19:12:49
  

  sync files from diff.git f1dbec24f9a9553e22659f6c592c91e96221f6b9

Download

• lib/diff_myers.c

• /* 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;
  }
  

Download