?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
portable: release 0.101
[got-portable.git] / lib / diff_myers.c
blob37b7f2b63c9f5a8e3a7ccee3cd4d60d698ef7c22
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). */
4 /*
5 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
6 *
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.
10 *
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.
18 */
19
20 #include "got_compat.h"
21
22 #include <stdbool.h>
23 #include <stdint.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <stdio.h>
27 #include <errno.h>
28
29 #include <arraylist.h>
30 #include <diff_main.h>
31
32 #include "diff_internal.h"
33 #include "diff_debug.h"
34
35 /* Myers' diff algorithm [1] is nicely explained in [2].
36 * [1] http://www.xmailserver.org/diff2.pdf
37 * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
38 *
39 * Myers approaches finding the smallest diff as a graph problem.
40 * The crux is that the original algorithm requires quadratic amount of memory:
41 * both sides' lengths added, and that squared. So if we're diffing lines of
42 * text, two files with 1000 lines each would blow up to a matrix of about
43 * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
44 * The solution is using Myers' "divide and conquer" extension algorithm, which
45 * does the original traversal from both ends of the files to reach a middle
46 * where these "snakes" touch, hence does not need to backtrace the traversal,
47 * and so gets away with only keeping a single column of that huge state matrix
48 * in memory.
49 */
50
51 struct diff_box {
52 unsigned int left_start;
53 unsigned int left_end;
54 unsigned int right_start;
55 unsigned int right_end;
56 };
57
58 /* If the two contents of a file are A B C D E and X B C Y,
59 * the Myers diff graph looks like:
60 *
61 * k0 k1
62 * \ \
63 * k-1 0 1 2 3 4 5
64 * \ A B C D E
65 * 0 o-o-o-o-o-o
66 * X | | | | | |
67 * 1 o-o-o-o-o-o
68 * B | |\| | | |
69 * 2 o-o-o-o-o-o
70 * C | | |\| | |
71 * 3 o-o-o-o-o-o
72 * Y | | | | | |\
73 * 4 o-o-o-o-o-o c1
74 * \ \
75 * c-1 c0
76 *
77 * Moving right means delete an atom from the left-hand-side,
78 * Moving down means add an atom from the right-hand-side.
79 * Diagonals indicate identical atoms on both sides, the challenge is to use as
80 * many diagonals as possible.
81 *
82 * The original Myers algorithm walks all the way from the top left to the
83 * bottom right, remembers all steps, and then backtraces to find the shortest
84 * path. However, that requires keeping the entire graph in memory, which needs
85 * quadratic space.
86 *
87 * Myers adds a variant that uses linear space -- note, not linear time, only
88 * linear space: walk forward and backward, find a meeting point in the middle,
89 * and recurse on the two separate sections. This is called "divide and
90 * conquer".
91 *
92 * d: the step number, starting with 0, a.k.a. the distance from the starting
93 * point.
94 * k: relative index in the state array for the forward scan, indicating on
95 * which diagonal through the diff graph we currently are.
96 * c: relative index in the state array for the backward scan, indicating the
97 * diagonal number from the bottom up.
98 *
99 * The "divide and conquer" traversal through the Myers graph looks like this:
100 *
101 * | d= 0 1 2 3 2 1 0
102 * ----+--------------------------------------------
103 * k= | c=
104 * 4 | 3
105 * |
106 * 3 | 3,0 5,2 2
107 * | / \
108 * 2 | 2,0 5,3 1
109 * | / \
110 * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
111 * | / / \ /
112 * 0 | -->0,0 3,3 4,4 -1
113 * | \ / /
114 * -1 | 0,1 1,2 3,4 -2
115 * | \ /
116 * -2 | 0,2 -3
117 * | \
118 * | 0,3
119 * | forward-> <-backward
120 *
121 * x,y pairs here are the coordinates in the Myers graph:
122 * x = atom index in left-side source, y = atom index in the right-side source.
123 *
124 * Only one forward column and one backward column are kept in mem, each need at
125 * most left.len + 1 + right.len items. Note that each d step occupies either
126 * the even or the odd items of a column: if e.g. the previous column is in the
127 * odd items, the next column is formed in the even items, without overwriting
128 * the previous column's results.
129 *
130 * Also note that from the diagonal index k and the x coordinate, the y
131 * coordinate can be derived:
132 * y = x - k
133 * Hence the state array only needs to keep the x coordinate, i.e. the position
134 * in the left-hand file, and the y coordinate, i.e. position in the right-hand
135 * file, is derived from the index in the state array.
136 *
137 * The two traces meet at 4,3, the first step (here found in the forward
138 * traversal) where a forward position is on or past a backward traced position
139 * on the same diagonal.
140 *
141 * This divides the problem space into:
142 *
143 * 0 1 2 3 4 5
144 * A B C D E
145 * 0 o-o-o-o-o
146 * X | | | | |
147 * 1 o-o-o-o-o
148 * B | |\| | |
149 * 2 o-o-o-o-o
150 * C | | |\| |
151 * 3 o-o-o-o-*-o *: forward and backward meet here
152 * Y | |
153 * 4 o-o
154 *
155 * Doing the same on each section lead to:
156 *
157 * 0 1 2 3 4 5
158 * A B C D E
159 * 0 o-o
160 * X | |
161 * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
162 * B \ f: then forward d=2 reaches here (sliding down the snake)
163 * 2 o As result, the box from b to f is found to be identical;
164 * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial
165 * 3 f-o tail 3,3 to 4,3.
166 *
167 * 3 o-*
168 * Y |
169 * 4 o *: forward and backward meet here
170 *
171 * and solving the last top left box gives:
172 *
173 * 0 1 2 3 4 5
174 * A B C D E -A
175 * 0 o-o +X
176 * X | B
177 * 1 o C
178 * B \ -D
179 * 2 o -E
180 * C \ +Y
181 * 3 o-o-o
182 * Y |
183 * 4 o
184 *
185 */
186
187 #define xk_to_y(X, K) ((X) - (K))
188 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
189 #define k_to_c(K, DELTA) ((K) + (DELTA))
190 #define c_to_k(C, DELTA) ((C) - (DELTA))
191
192 /* Do one forwards step in the "divide and conquer" graph traversal.
193 * left: the left side to diff.
194 * right: the right side to diff against.
195 * kd_forward: the traversal state for forwards traversal, modified by this
196 * function.
197 * This is carried over between invocations with increasing d.
198 * kd_forward points at the center of the state array, allowing
199 * negative indexes.
200 * kd_backward: the traversal state for backwards traversal, to find a meeting
201 * point.
202 * Since forwards is done first, kd_backward will be valid for d -
203 * 1, not d.
204 * kd_backward points at the center of the state array, allowing
205 * negative indexes.
206 * d: Step or distance counter, indicating for what value of d the kd_forward
207 * should be populated.
208 * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
209 * be for d == 0.
210 * meeting_snake: resulting meeting point, if any.
211 * Return true when a meeting point has been identified.
212 */
213 static int
214 diff_divide_myers_forward(bool *found_midpoint,
215 struct diff_data *left, struct diff_data *right,
216 int *kd_forward, int *kd_backward, int d,
217 struct diff_box *meeting_snake)
218 {
219 int delta = (int)right->atoms.len - (int)left->atoms.len;
220 int k;
221 int x;
222 int prev_x;
223 int prev_y;
224 int x_before_slide;
225 *found_midpoint = false;
226
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 < 0) {
232 /* We are traversing negatively, and already
233 * below the entire graph, nothing will come of
234 * this. */
235 debug(" break\n");
236 break;
237 }
238 debug(" continue\n");
239 continue;
240 }
241 if (d == 0) {
242 /* This is the initializing step. There is no prev_k
243 * yet, get the initial x from the top left of the Myers
244 * graph. */
245 x = 0;
246 prev_x = x;
247 prev_y = xk_to_y(x, k);
248 }
249 /* Favoring "-" lines first means favoring moving rightwards in
250 * the Myers graph.
251 * For this, all k should derive from k - 1, only the bottom
252 * most k derive from k + 1:
253 *
254 * | d= 0 1 2
255 * ----+----------------
256 * k= |
257 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
258 * | /
259 * 1 | 1,0
260 * | /
261 * 0 | -->0,0 3,3
262 * | \\ /
263 * -1 | 0,1 <-- bottom most for d=1 from
264 * | \\ prev_k = -1 + 1 = 0
265 * -2 | 0,2 <-- bottom most for d=2 from
266 * prev_k = -2 + 1 = -1
267 *
268 * Except when a k + 1 from a previous run already means a
269 * further advancement in the graph.
270 * If k == d, there is no k + 1 and k - 1 is the only option.
271 * If k < d, use k + 1 in case that yields a larger x. Also use
272 * k + 1 if k - 1 is outside the graph.
273 */
274 else if (k > -d
275 && (k == d
276 || (k - 1 >= -(int)right->atoms.len
277 && kd_forward[k - 1] >= kd_forward[k + 1]))) {
278 /* Advance from k - 1.
279 * From position prev_k, step to the right in the Myers
280 * graph: x += 1.
281 */
282 int prev_k = k - 1;
283 prev_x = kd_forward[prev_k];
284 prev_y = xk_to_y(prev_x, prev_k);
285 x = prev_x + 1;
286 } else {
287 /* The bottom most one.
288 * From position prev_k, step to the bottom in the Myers
289 * graph: y += 1.
290 * Incrementing y is achieved by decrementing k while
291 * keeping the same x.
292 * (since we're deriving y from y = x - k).
293 */
294 int prev_k = k + 1;
295 prev_x = kd_forward[prev_k];
296 prev_y = xk_to_y(prev_x, prev_k);
297 x = prev_x;
298 }
299
300 x_before_slide = x;
301 /* Slide down any snake that we might find here. */
302 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) {
303 bool same;
304 int r = diff_atom_same(&same,
305 &left->atoms.head[x],
306 &right->atoms.head[
307 xk_to_y(x, k)]);
308 if (r)
309 return r;
310 if (!same)
311 break;
312 x++;
313 }
314 kd_forward[k] = x;
315 #if 0
316 if (x_before_slide != x) {
317 debug(" down %d similar lines\n", x - x_before_slide);
318 }
319
320 #if DEBUG
321 {
322 int fi;
323 for (fi = d; fi >= k; fi--) {
324 debug("kd_forward[%d] = (%d, %d)\n", fi,
325 kd_forward[fi], kd_forward[fi] - fi);
326 }
327 }
328 #endif
329 #endif
330
331 if (x < 0 || x > left->atoms.len
332 || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
333 continue;
334
335 /* Figured out a new forwards traversal, see if this has gone
336 * onto or even past a preceding backwards traversal.
337 *
338 * If the delta in length is odd, then d and backwards_d hit the
339 * same state indexes:
340 * | d= 0 1 2 1 0
341 * ----+---------------- ----------------
342 * k= | c=
343 * 4 | 3
344 * |
345 * 3 | 2
346 * | same
347 * 2 | 2,0====5,3 1
348 * | / \
349 * 1 | 1,0 5,4<-- 0
350 * | / /
351 * 0 | -->0,0 3,3====4,4 -1
352 * | \ /
353 * -1 | 0,1 -2
354 * | \
355 * -2 | 0,2 -3
356 * |
357 *
358 * If the delta is even, they end up off-by-one, i.e. on
359 * different diagonals:
360 *
361 * | d= 0 1 2 1 0
362 * ----+---------------- ----------------
363 * | c=
364 * 3 | 3
365 * |
366 * 2 | 2,0 off 2
367 * | / \\
368 * 1 | 1,0 4,3 1
369 * | / // \
370 * 0 | -->0,0 3,3 4,4<-- 0
371 * | \ / /
372 * -1 | 0,1 3,4 -1
373 * | \ //
374 * -2 | 0,2 -2
375 * |
376 *
377 * So in the forward path, we can only match up diagonals when
378 * the delta is odd.
379 */
380 if ((delta & 1) == 0)
381 continue;
382 /* Forwards is done first, so the backwards one was still at
383 * d - 1. Can't do this for d == 0. */
384 int backwards_d = d - 1;
385 if (backwards_d < 0)
386 continue;
387
388 /* If both sides have the same length, forward and backward
389 * start on the same diagonal, meaning the backwards state index
390 * c == k.
391 * As soon as the lengths are not the same, the backwards
392 * traversal starts on a different diagonal, and c = k shifted
393 * by the difference in length.
394 */
395 int c = k_to_c(k, delta);
396
397 /* When the file sizes are very different, the traversal trees
398 * start on far distant diagonals.
399 * They don't necessarily meet straight on. See whether this
400 * forward value is on a diagonal that is also valid in
401 * kd_backward[], and match them if so. */
402 if (c >= -backwards_d && c <= backwards_d) {
403 /* Current k is on a diagonal that exists in
404 * kd_backward[]. If the two x positions have met or
405 * passed (forward walked onto or past backward), then
406 * we've found a midpoint / a mid-box.
407 *
408 * When forwards and backwards traversals meet, the
409 * endpoints of the mid-snake are not the two points in
410 * kd_forward and kd_backward, but rather the section
411 * that was slid (if any) of the current
412 * forward/backward traversal only.
413 *
414 * For example:
415 *
416 * o
417 * \
418 * o
419 * \
420 * o
421 * \
422 * o
423 * \
424 * X o o
425 * | | |
426 * o-o-o o
427 * \|
428 * M
429 * \
430 * o
431 * \
432 * A o
433 * | |
434 * o-o-o
435 *
436 * The forward traversal reached M from the top and slid
437 * downwards to A. The backward traversal already
438 * reached X, which is not a straight line from M
439 * anymore, so picking a mid-snake from M to X would
440 * yield a mistake.
441 *
442 * The correct mid-snake is between M and A. M is where
443 * the forward traversal hit the diagonal that the
444 * backward traversal has already passed, and A is what
445 * it reaches when sliding down identical lines.
446 */
447 int backward_x = kd_backward[c];
448 if (x >= backward_x) {
449 if (x_before_slide != x) {
450 /* met after sliding up a mid-snake */
451 *meeting_snake = (struct diff_box){
452 .left_start = x_before_slide,
453 .left_end = x,
454 .right_start = xc_to_y(x_before_slide,
455 c, delta),
456 .right_end = xk_to_y(x, k),
457 };
458 } else {
459 /* met after a side step, non-identical
460 * line. Mark that as box divider
461 * instead. This makes sure that
462 * myers_divide never returns the same
463 * box that came as input, avoiding
464 * "infinite" looping. */
465 *meeting_snake = (struct diff_box){
466 .left_start = prev_x,
467 .left_end = x,
468 .right_start = prev_y,
469 .right_end = xk_to_y(x, k),
470 };
471 }
472 debug("HIT x=(%u,%u) - y=(%u,%u)\n",
473 meeting_snake->left_start,
474 meeting_snake->right_start,
475 meeting_snake->left_end,
476 meeting_snake->right_end);
477 debug_dump_myers_graph(left, right, NULL,
478 kd_forward, d,
479 kd_backward, d-1);
480 *found_midpoint = true;
481 return 0;
482 }
483 }
484 }
485
486 return 0;
487 }
488
489 /* Do one backwards step in the "divide and conquer" graph traversal.
490 * left: the left side to diff.
491 * right: the right side to diff against.
492 * kd_forward: the traversal state for forwards traversal, to find a meeting
493 * point.
494 * Since forwards is done first, after this, both kd_forward and
495 * kd_backward will be valid for d.
496 * kd_forward points at the center of the state array, allowing
497 * negative indexes.
498 * kd_backward: the traversal state for backwards traversal, to find a meeting
499 * point.
500 * This is carried over between invocations with increasing d.
501 * kd_backward points at the center of the state array, allowing
502 * negative indexes.
503 * d: Step or distance counter, indicating for what value of d the kd_backward
504 * should be populated.
505 * Before the first invocation, kd_backward[0] shall point at the bottom
506 * right of the Myers graph (left.len, right.len).
507 * The first invocation will be for d == 1.
508 * meeting_snake: resulting meeting point, if any.
509 * Return true when a meeting point has been identified.
510 */
511 static int
512 diff_divide_myers_backward(bool *found_midpoint,
513 struct diff_data *left, struct diff_data *right,
514 int *kd_forward, int *kd_backward, int d,
515 struct diff_box *meeting_snake)
516 {
517 int delta = (int)right->atoms.len - (int)left->atoms.len;
518 int c;
519 int x;
520 int prev_x;
521 int prev_y;
522 int x_before_slide;
523
524 *found_midpoint = false;
525
526 for (c = d; c >= -d; c -= 2) {
527 if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
528 /* This diagonal is completely outside of the Myers
529 * graph, don't calculate it. */
530 if (c < 0) {
531 /* We are traversing negatively, and already
532 * below the entire graph, nothing will come of
533 * this. */
534 break;
535 }
536 continue;
537 }
538 if (d == 0) {
539 /* This is the initializing step. There is no prev_c
540 * yet, get the initial x from the bottom right of the
541 * Myers graph. */
542 x = left->atoms.len;
543 prev_x = x;
544 prev_y = xc_to_y(x, c, delta);
545 }
546 /* Favoring "-" lines first means favoring moving rightwards in
547 * the Myers graph.
548 * For this, all c should derive from c - 1, only the bottom
549 * most c derive from c + 1:
550 *
551 * 2 1 0
552 * ---------------------------------------------------
553 * c=
554 * 3
555 *
556 * from prev_c = c - 1 --> 5,2 2
557 * \
558 * 5,3 1
559 * \
560 * 4,3 5,4<-- 0
561 * \ /
562 * bottom most for d=1 from c + 1 --> 4,4 -1
563 * /
564 * bottom most for d=2 --> 3,4 -2
565 *
566 * Except when a c + 1 from a previous run already means a
567 * further advancement in the graph.
568 * If c == d, there is no c + 1 and c - 1 is the only option.
569 * If c < d, use c + 1 in case that yields a larger x.
570 * Also use c + 1 if c - 1 is outside the graph.
571 */
572 else if (c > -d && (c == d
573 || (c - 1 >= -(int)right->atoms.len
574 && kd_backward[c - 1] <= kd_backward[c + 1]))) {
575 /* A top one.
576 * From position prev_c, step upwards in the Myers
577 * graph: y -= 1.
578 * Decrementing y is achieved by incrementing c while
579 * keeping the same x. (since we're deriving y from
580 * y = x - c + delta).
581 */
582 int prev_c = c - 1;
583 prev_x = kd_backward[prev_c];
584 prev_y = xc_to_y(prev_x, prev_c, delta);
585 x = prev_x;
586 } else {
587 /* The bottom most one.
588 * From position prev_c, step to the left in the Myers
589 * graph: x -= 1.
590 */
591 int prev_c = c + 1;
592 prev_x = kd_backward[prev_c];
593 prev_y = xc_to_y(prev_x, prev_c, delta);
594 x = prev_x - 1;
595 }
596
597 /* Slide up any snake that we might find here (sections of
598 * identical lines on both sides). */
599 #if 0
600 debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c,
601 delta),
602 xc_to_y(x, c, delta)-1);
603 if (x > 0) {
604 debug(" l=");
605 debug_dump_atom(left, right, &left->atoms.head[x-1]);
606 }
607 if (xc_to_y(x, c, delta) > 0) {
608 debug(" r=");
609 debug_dump_atom(right, left,
610 &right->atoms.head[xc_to_y(x, c, delta)-1]);
611 }
612 #endif
613 x_before_slide = x;
614 while (x > 0 && xc_to_y(x, c, delta) > 0) {
615 bool same;
616 int r = diff_atom_same(&same,
617 &left->atoms.head[x-1],
618 &right->atoms.head[
619 xc_to_y(x, c, delta)-1]);
620 if (r)
621 return r;
622 if (!same)
623 break;
624 x--;
625 }
626 kd_backward[c] = x;
627 #if 0
628 if (x_before_slide != x) {
629 debug(" up %d similar lines\n", x_before_slide - x);
630 }
631
632 if (DEBUG) {
633 int fi;
634 for (fi = d; fi >= c; fi--) {
635 debug("kd_backward[%d] = (%d, %d)\n",
636 fi,
637 kd_backward[fi],
638 kd_backward[fi] - fi + delta);
639 }
640 }
641 #endif
642
643 if (x < 0 || x > left->atoms.len
644 || xc_to_y(x, c, delta) < 0
645 || xc_to_y(x, c, delta) > right->atoms.len)
646 continue;
647
648 /* Figured out a new backwards traversal, see if this has gone
649 * onto or even past a preceding forwards traversal.
650 *
651 * If the delta in length is even, then d and backwards_d hit
652 * the same state indexes -- note how this is different from in
653 * the forwards traversal, because now both d are the same:
654 *
655 * | d= 0 1 2 2 1 0
656 * ----+---------------- --------------------
657 * k= | c=
658 * 4 |
659 * |
660 * 3 | 3
661 * | same
662 * 2 | 2,0====5,2 2
663 * | / \
664 * 1 | 1,0 5,3 1
665 * | / / \
666 * 0 | -->0,0 3,3====4,3 5,4<-- 0
667 * | \ / /
668 * -1 | 0,1 4,4 -1
669 * | \
670 * -2 | 0,2 -2
671 * |
672 * -3
673 * If the delta is odd, they end up off-by-one, i.e. on
674 * different diagonals.
675 * So in the backward path, we can only match up diagonals when
676 * the delta is even.
677 */
678 if ((delta & 1) != 0)
679 continue;
680 /* Forwards was done first, now both d are the same. */
681 int forwards_d = d;
682
683 /* As soon as the lengths are not the same, the
684 * backwards traversal starts on a different diagonal,
685 * and c = k shifted by the difference in length.
686 */
687 int k = c_to_k(c, delta);
688
689 /* When the file sizes are very different, the traversal trees
690 * start on far distant diagonals.
691 * They don't necessarily meet straight on. See whether this
692 * backward value is also on a valid diagonal in kd_forward[],
693 * and match them if so. */
694 if (k >= -forwards_d && k <= forwards_d) {
695 /* Current c is on a diagonal that exists in
696 * kd_forward[]. If the two x positions have met or
697 * passed (backward walked onto or past forward), then
698 * we've found a midpoint / a mid-box.
699 *
700 * When forwards and backwards traversals meet, the
701 * endpoints of the mid-snake are not the two points in
702 * kd_forward and kd_backward, but rather the section
703 * that was slid (if any) of the current
704 * forward/backward traversal only.
705 *
706 * For example:
707 *
708 * o-o-o
709 * | |
710 * o A
711 * | \
712 * o o
713 * \
714 * M
715 * |\
716 * o o-o-o
717 * | | |
718 * o o X
719 * \
720 * o
721 * \
722 * o
723 * \
724 * o
725 *
726 * The backward traversal reached M from the bottom and
727 * slid upwards. The forward traversal already reached
728 * X, which is not a straight line from M anymore, so
729 * picking a mid-snake from M to X would yield a
730 * mistake.
731 *
732 * The correct mid-snake is between M and A. M is where
733 * the backward traversal hit the diagonal that the
734 * forwards traversal has already passed, and A is what
735 * it reaches when sliding up identical lines.
736 */
737
738 int forward_x = kd_forward[k];
739 if (forward_x >= x) {
740 if (x_before_slide != x) {
741 /* met after sliding down a mid-snake */
742 *meeting_snake = (struct diff_box){
743 .left_start = x,
744 .left_end = x_before_slide,
745 .right_start = xc_to_y(x, c, delta),
746 .right_end = xk_to_y(x_before_slide, k),
747 };
748 } else {
749 /* met after a side step, non-identical
750 * line. Mark that as box divider
751 * instead. This makes sure that
752 * myers_divide never returns the same
753 * box that came as input, avoiding
754 * "infinite" looping. */
755 *meeting_snake = (struct diff_box){
756 .left_start = x,
757 .left_end = prev_x,
758 .right_start = xc_to_y(x, c, delta),
759 .right_end = prev_y,
760 };
761 }
762 debug("HIT x=%u,%u - y=%u,%u\n",
763 meeting_snake->left_start,
764 meeting_snake->right_start,
765 meeting_snake->left_end,
766 meeting_snake->right_end);
767 debug_dump_myers_graph(left, right, NULL,
768 kd_forward, d,
769 kd_backward, d);
770 *found_midpoint = true;
771 return 0;
772 }
773 }
774 }
775 return 0;
776 }
777
778 /* Integer square root approximation */
779 static int
780 shift_sqrt(int val)
781 {
782 int i;
783 for (i = 1; val > 0; val >>= 2)
784 i <<= 1;
785 return i;
786 }
787
788 #define DIFF_EFFORT_MIN 1024
789
790 /* Myers "Divide et Impera": tracing forwards from the start and backwards from
791 * the end to find a midpoint that divides the problem into smaller chunks.
792 * Requires only linear amounts of memory. */
793 int
794 diff_algo_myers_divide(const struct diff_algo_config *algo_config,
795 struct diff_state *state)
796 {
797 int rc = ENOMEM;
798 struct diff_data *left = &state->left;
799 struct diff_data *right = &state->right;
800 int *kd_buf;
801
802 debug("\n** %s\n", __func__);
803 debug("left:\n");
804 debug_dump(left);
805 debug("right:\n");
806 debug_dump(right);
807
808 /* Allocate two columns of a Myers graph, one for the forward and one
809 * for the backward traversal. */
810 unsigned int max = left->atoms.len + right->atoms.len;
811 size_t kd_len = max + 1;
812 size_t kd_buf_size = kd_len << 1;
813
814 if (state->kd_buf_size < kd_buf_size) {
815 kd_buf = reallocarray(state->kd_buf, kd_buf_size,
816 sizeof(int));
817 if (!kd_buf)
818 return ENOMEM;
819 state->kd_buf = kd_buf;
820 state->kd_buf_size = kd_buf_size;
821 } else
822 kd_buf = state->kd_buf;
823 int i;
824 for (i = 0; i < kd_buf_size; i++)
825 kd_buf[i] = -1;
826 int *kd_forward = kd_buf;
827 int *kd_backward = kd_buf + kd_len;
828 int max_effort = shift_sqrt(max/2);
829
830 if (max_effort < DIFF_EFFORT_MIN)
831 max_effort = DIFF_EFFORT_MIN;
832
833 /* The 'k' axis in Myers spans positive and negative indexes, so point
834 * the kd to the middle.
835 * It is then possible to index from -max/2 .. max/2. */
836 kd_forward += max/2;
837 kd_backward += max/2;
838
839 int d;
840 struct diff_box mid_snake = {};
841 bool found_midpoint = false;
842 for (d = 0; d <= (max/2); d++) {
843 int r;
844 r = diff_divide_myers_forward(&found_midpoint, left, right,
845 kd_forward, kd_backward, d,
846 &mid_snake);
847 if (r)
848 return r;
849 if (found_midpoint)
850 break;
851 r = diff_divide_myers_backward(&found_midpoint, left, right,
852 kd_forward, kd_backward, d,
853 &mid_snake);
854 if (r)
855 return r;
856 if (found_midpoint)
857 break;
858
859 /* Limit the effort spent looking for a mid snake. If files have
860 * very few lines in common, the effort spent to find nice mid
861 * snakes is just not worth it, the diff result will still be
862 * essentially minus everything on the left, plus everything on
863 * the right, with a few useless matches here and there. */
864 if (d > max_effort) {
865 /* pick the furthest reaching point from
866 * kd_forward and kd_backward, and use that as a
867 * midpoint, to not step into another diff algo
868 * recursion with unchanged box. */
869 int delta = (int)right->atoms.len - (int)left->atoms.len;
870 int x = 0;
871 int y;
872 int i;
873 int best_forward_i = 0;
874 int best_forward_distance = 0;
875 int best_backward_i = 0;
876 int best_backward_distance = 0;
877 int distance;
878 int best_forward_x;
879 int best_forward_y;
880 int best_backward_x;
881 int best_backward_y;
882
883 debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort);
884 debug_dump_myers_graph(left, right, NULL,
885 kd_forward, d,
886 kd_backward, d);
887
888 for (i = d; i >= -d; i -= 2) {
889 if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) {
890 x = kd_forward[i];
891 y = xk_to_y(x, i);
892 distance = x + y;
893 if (distance > best_forward_distance) {
894 best_forward_distance = distance;
895 best_forward_i = i;
896 }
897 }
898
899 if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) {
900 x = kd_backward[i];
901 y = xc_to_y(x, i, delta);
902 distance = (right->atoms.len - x)
903 + (left->atoms.len - y);
904 if (distance >= best_backward_distance) {
905 best_backward_distance = distance;
906 best_backward_i = i;
907 }
908 }
909 }
910
911 /* The myers-divide didn't meet in the middle. We just
912 * figured out the places where the forward path
913 * advanced the most, and the backward path advanced the
914 * most. Just divide at whichever one of those two is better.
915 *
916 * o-o
917 * |
918 * o
919 * \
920 * o
921 * \
922 * F <-- cut here
923 *
924 *
925 *
926 * or here --> B
927 * \
928 * o
929 * \
930 * o
931 * |
932 * o-o
933 */
934 best_forward_x = kd_forward[best_forward_i];
935 best_forward_y = xk_to_y(best_forward_x, best_forward_i);
936 best_backward_x = kd_backward[best_backward_i];
937 best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta);
938
939 if (best_forward_distance >= best_backward_distance) {
940 x = best_forward_x;
941 y = best_forward_y;
942 } else {
943 x = best_backward_x;
944 y = best_backward_y;
945 }
946
947 debug("max_effort cut at x=%d y=%d\n", x, y);
948 if (x < 0 || y < 0
949 || x > left->atoms.len || y > right->atoms.len)
950 break;
951
952 found_midpoint = true;
953 mid_snake = (struct diff_box){
954 .left_start = x,
955 .left_end = x,
956 .right_start = y,
957 .right_end = y,
958 };
959 break;
960 }
961 }
962
963 if (!found_midpoint) {
964 /* Divide and conquer failed to find a meeting point. Use the
965 * fallback_algo defined in the algo_config (leave this to the
966 * caller). This is just paranoia/sanity, we normally should
967 * always find a midpoint.
968 */
969 debug(" no midpoint \n");
970 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
971 goto return_rc;
972 } else {
973 debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
974 mid_snake.left_start, mid_snake.left_end, left->atoms.len,
975 mid_snake.right_start, mid_snake.right_end,
976 right->atoms.len);
977
978 /* Section before the mid-snake. */
979 debug("Section before the mid-snake\n");
980
981 struct diff_atom *left_atom = &left->atoms.head[0];
982 unsigned int left_section_len = mid_snake.left_start;
983 struct diff_atom *right_atom = &right->atoms.head[0];
984 unsigned int right_section_len = mid_snake.right_start;
985
986 if (left_section_len && right_section_len) {
987 /* Record an unsolved chunk, the caller will apply
988 * inner_algo() on this chunk. */
989 if (!diff_state_add_chunk(state, false,
990 left_atom, left_section_len,
991 right_atom,
992 right_section_len))
993 goto return_rc;
994 } else if (left_section_len && !right_section_len) {
995 /* Only left atoms and none on the right, they form a
996 * "minus" chunk, then. */
997 if (!diff_state_add_chunk(state, true,
998 left_atom, left_section_len,
999 right_atom, 0))
1000 goto return_rc;
1001 } else if (!left_section_len && right_section_len) {
1002 /* No left atoms, only atoms on the right, they form a
1003 * "plus" chunk, then. */
1004 if (!diff_state_add_chunk(state, true,
1005 left_atom, 0,
1006 right_atom,
1007 right_section_len))
1008 goto return_rc;
1009 }
1010 /* else: left_section_len == 0 and right_section_len == 0, i.e.
1011 * nothing before the mid-snake. */
1012
1013 if (mid_snake.left_end > mid_snake.left_start
1014 || mid_snake.right_end > mid_snake.right_start) {
1015 /* The midpoint is a section of identical data on both
1016 * sides, or a certain differing line: that section
1017 * immediately becomes a solved chunk. */
1018 debug("the mid-snake\n");
1019 if (!diff_state_add_chunk(state, true,
1020 &left->atoms.head[mid_snake.left_start],
1021 mid_snake.left_end - mid_snake.left_start,
1022 &right->atoms.head[mid_snake.right_start],
1023 mid_snake.right_end - mid_snake.right_start))
1024 goto return_rc;
1025 }
1026
1027 /* Section after the mid-snake. */
1028 debug("Section after the mid-snake\n");
1029 debug(" left_end %u right_end %u\n",
1030 mid_snake.left_end, mid_snake.right_end);
1031 debug(" left_count %u right_count %u\n",
1032 left->atoms.len, right->atoms.len);
1033 left_atom = &left->atoms.head[mid_snake.left_end];
1034 left_section_len = left->atoms.len - mid_snake.left_end;
1035 right_atom = &right->atoms.head[mid_snake.right_end];
1036 right_section_len = right->atoms.len - mid_snake.right_end;
1037
1038 if (left_section_len && right_section_len) {
1039 /* Record an unsolved chunk, the caller will apply
1040 * inner_algo() on this chunk. */
1041 if (!diff_state_add_chunk(state, false,
1042 left_atom, left_section_len,
1043 right_atom,
1044 right_section_len))
1045 goto return_rc;
1046 } else if (left_section_len && !right_section_len) {
1047 /* Only left atoms and none on the right, they form a
1048 * "minus" chunk, then. */
1049 if (!diff_state_add_chunk(state, true,
1050 left_atom, left_section_len,
1051 right_atom, 0))
1052 goto return_rc;
1053 } else if (!left_section_len && right_section_len) {
1054 /* No left atoms, only atoms on the right, they form a
1055 * "plus" chunk, then. */
1056 if (!diff_state_add_chunk(state, true,
1057 left_atom, 0,
1058 right_atom,
1059 right_section_len))
1060 goto return_rc;
1061 }
1062 /* else: left_section_len == 0 and right_section_len == 0, i.e.
1063 * nothing after the mid-snake. */
1064 }
1065
1066 rc = DIFF_RC_OK;
1067
1068 return_rc:
1069 debug("** END %s\n", __func__);
1070 return rc;
1071 }
1072
1073 /* Myers Diff tracing from the start all the way through to the end, requiring
1074 * quadratic amounts of memory. This can fail if the required space surpasses
1075 * algo_config->permitted_state_size. */
1076 int
1077 diff_algo_myers(const struct diff_algo_config *algo_config,
1078 struct diff_state *state)
1079 {
1080 /* do a diff_divide_myers_forward() without a _backward(), so that it
1081 * walks forward across the entire files to reach the end. Keep each
1082 * run's state, and do a final backtrace. */
1083 int rc = ENOMEM;
1084 struct diff_data *left = &state->left;
1085 struct diff_data *right = &state->right;
1086 int *kd_buf;
1087
1088 debug("\n** %s\n", __func__);
1089 debug("left:\n");
1090 debug_dump(left);
1091 debug("right:\n");
1092 debug_dump(right);
1093 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
1094
1095 /* Allocate two columns of a Myers graph, one for the forward and one
1096 * for the backward traversal. */
1097 unsigned int max = left->atoms.len + right->atoms.len;
1098 size_t kd_len = max + 1 + max;
1099 size_t kd_buf_size = kd_len * kd_len;
1100 size_t kd_state_size = kd_buf_size * sizeof(int);
1101 debug("state size: %zu\n", kd_state_size);
1102 if (kd_buf_size < kd_len /* overflow? */
1103 || (SIZE_MAX / kd_len ) < kd_len
1104 || kd_state_size > algo_config->permitted_state_size) {
1105 debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
1106 kd_state_size, algo_config->permitted_state_size);
1107 return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1108 }
1109
1110 if (state->kd_buf_size < kd_buf_size) {
1111 kd_buf = reallocarray(state->kd_buf, kd_buf_size,
1112 sizeof(int));
1113 if (!kd_buf)
1114 return ENOMEM;
1115 state->kd_buf = kd_buf;
1116 state->kd_buf_size = kd_buf_size;
1117 } else
1118 kd_buf = state->kd_buf;
1119
1120 int i;
1121 for (i = 0; i < kd_buf_size; i++)
1122 kd_buf[i] = -1;
1123
1124 /* The 'k' axis in Myers spans positive and negative indexes, so point
1125 * the kd to the middle.
1126 * It is then possible to index from -max .. max. */
1127 int *kd_origin = kd_buf + max;
1128 int *kd_column = kd_origin;
1129
1130 int d;
1131 int backtrack_d = -1;
1132 int backtrack_k = 0;
1133 int k;
1134 int x, y;
1135 for (d = 0; d <= max; d++, kd_column += kd_len) {
1136 debug("-- %s d=%d\n", __func__, d);
1137
1138 for (k = d; k >= -d; k -= 2) {
1139 if (k < -(int)right->atoms.len
1140 || k > (int)left->atoms.len) {
1141 /* This diagonal is completely outside of the
1142 * Myers graph, don't calculate it. */
1143 if (k < -(int)right->atoms.len)
1144 debug(" %d k <"
1145 " -(int)right->atoms.len %d\n",
1146 k, -(int)right->atoms.len);
1147 else
1148 debug(" %d k > left->atoms.len %d\n", k,
1149 left->atoms.len);
1150 if (k < 0) {
1151 /* We are traversing negatively, and
1152 * already below the entire graph,
1153 * nothing will come of this. */
1154 debug(" break\n");
1155 break;
1156 }
1157 debug(" continue\n");
1158 continue;
1159 }
1160
1161 if (d == 0) {
1162 /* This is the initializing step. There is no
1163 * prev_k yet, get the initial x from the top
1164 * left of the Myers graph. */
1165 x = 0;
1166 } else {
1167 int *kd_prev_column = kd_column - kd_len;
1168
1169 /* Favoring "-" lines first means favoring
1170 * moving rightwards in the Myers graph.
1171 * For this, all k should derive from k - 1,
1172 * only the bottom most k derive from k + 1:
1173 *
1174 * | d= 0 1 2
1175 * ----+----------------
1176 * k= |
1177 * 2 | 2,0 <-- from
1178 * | / prev_k = 2 - 1 = 1
1179 * 1 | 1,0
1180 * | /
1181 * 0 | -->0,0 3,3
1182 * | \\ /
1183 * -1 | 0,1 <-- bottom most for d=1
1184 * | \\ from prev_k = -1+1 = 0
1185 * -2 | 0,2 <-- bottom most for
1186 * d=2 from
1187 * prev_k = -2+1 = -1
1188 *
1189 * Except when a k + 1 from a previous run
1190 * already means a further advancement in the
1191 * graph.
1192 * If k == d, there is no k + 1 and k - 1 is the
1193 * only option.
1194 * If k < d, use k + 1 in case that yields a
1195 * larger x. Also use k + 1 if k - 1 is outside
1196 * the graph.
1197 */
1198 if (k > -d
1199 && (k == d
1200 || (k - 1 >= -(int)right->atoms.len
1201 && kd_prev_column[k - 1]
1202 >= kd_prev_column[k + 1]))) {
1203 /* Advance from k - 1.
1204 * From position prev_k, step to the
1205 * right in the Myers graph: x += 1.
1206 */
1207 int prev_k = k - 1;
1208 int prev_x = kd_prev_column[prev_k];
1209 x = prev_x + 1;
1210 } else {
1211 /* The bottom most one.
1212 * From position prev_k, step to the
1213 * bottom in the Myers graph: y += 1.
1214 * Incrementing y is achieved by
1215 * decrementing k while keeping the same
1216 * x. (since we're deriving y from y =
1217 * x - k).
1218 */
1219 int prev_k = k + 1;
1220 int prev_x = kd_prev_column[prev_k];
1221 x = prev_x;
1222 }
1223 }
1224
1225 /* Slide down any snake that we might find here. */
1226 while (x < left->atoms.len
1227 && xk_to_y(x, k) < right->atoms.len) {
1228 bool same;
1229 int r = diff_atom_same(&same,
1230 &left->atoms.head[x],
1231 &right->atoms.head[
1232 xk_to_y(x, k)]);
1233 if (r)
1234 return r;
1235 if (!same)
1236 break;
1237 x++;
1238 }
1239 kd_column[k] = x;
1240
1241 if (x == left->atoms.len
1242 && xk_to_y(x, k) == right->atoms.len) {
1243 /* Found a path */
1244 backtrack_d = d;
1245 backtrack_k = k;
1246 debug("Reached the end at d = %d, k = %d\n",
1247 backtrack_d, backtrack_k);
1248 break;
1249 }
1250 }
1251
1252 if (backtrack_d >= 0)
1253 break;
1254 }
1255
1256 debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
1257
1258 /* backtrack. A matrix spanning from start to end of the file is ready:
1259 *
1260 * | d= 0 1 2 3 4
1261 * ----+---------------------------------
1262 * k= |
1263 * 3 |
1264 * |
1265 * 2 | 2,0
1266 * | /
1267 * 1 | 1,0 4,3
1268 * | / / \
1269 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
1270 * | \ / \
1271 * -1 | 0,1 3,4
1272 * | \
1273 * -2 | 0,2
1274 * |
1275 *
1276 * From (4,4) backwards, find the previous position that is the largest, and remember it.
1277 *
1278 */
1279 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
1280 x = kd_column[k];
1281 y = xk_to_y(x, k);
1282
1283 /* When the best position is identified, remember it for that
1284 * kd_column.
1285 * That kd_column is no longer needed otherwise, so just
1286 * re-purpose kd_column[0] = x and kd_column[1] = y,
1287 * so that there is no need to allocate more memory.
1288 */
1289 kd_column[0] = x;
1290 kd_column[1] = y;
1291 debug("Backtrack d=%d: xy=(%d, %d)\n",
1292 d, kd_column[0], kd_column[1]);
1293
1294 /* Don't access memory before kd_buf */
1295 if (d == 0)
1296 break;
1297 int *kd_prev_column = kd_column - kd_len;
1298
1299 /* When y == 0, backtracking downwards (k-1) is the only way.
1300 * When x == 0, backtracking upwards (k+1) is the only way.
1301 *
1302 * | d= 0 1 2 3 4
1303 * ----+---------------------------------
1304 * k= |
1305 * 3 |
1306 * | ..y == 0
1307 * 2 | 2,0
1308 * | /
1309 * 1 | 1,0 4,3
1310 * | / / \
1311 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4,
1312 * | \ / \ backtrack_k = 0
1313 * -1 | 0,1 3,4
1314 * | \
1315 * -2 | 0,2__
1316 * | x == 0
1317 */
1318 if (y == 0
1319 || (x > 0
1320 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
1321 k = k - 1;
1322 debug("prev k=k-1=%d x=%d y=%d\n",
1323 k, kd_prev_column[k],
1324 xk_to_y(kd_prev_column[k], k));
1325 } else {
1326 k = k + 1;
1327 debug("prev k=k+1=%d x=%d y=%d\n",
1328 k, kd_prev_column[k],
1329 xk_to_y(kd_prev_column[k], k));
1330 }
1331 kd_column = kd_prev_column;
1332 }
1333
1334 /* Forwards again, this time recording the diff chunks.
1335 * Definitely start from 0,0. kd_column[0] may actually point to the
1336 * bottom of a snake starting at 0,0 */
1337 x = 0;
1338 y = 0;
1339
1340 kd_column = kd_origin;
1341 for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
1342 int next_x = kd_column[0];
1343 int next_y = kd_column[1];
1344 debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
1345 x, y, next_x, next_y);
1346
1347 struct diff_atom *left_atom = &left->atoms.head[x];
1348 int left_section_len = next_x - x;
1349 struct diff_atom *right_atom = &right->atoms.head[y];
1350 int right_section_len = next_y - y;
1351
1352 rc = ENOMEM;
1353 if (left_section_len && right_section_len) {
1354 /* This must be a snake slide.
1355 * Snake slides have a straight line leading into them
1356 * (except when starting at (0,0)). Find out whether the
1357 * lead-in is horizontal or vertical:
1358 *
1359 * left
1360 * ---------->
1361 * |
1362 * r| o-o o
1363 * i| \ |
1364 * g| o o
1365 * h| \ \
1366 * t| o o
1367 * v
1368 *
1369 * If left_section_len > right_section_len, the lead-in
1370 * is horizontal, meaning first remove one atom from the
1371 * left before sliding down the snake.
1372 * If right_section_len > left_section_len, the lead-in
1373 * is vetical, so add one atom from the right before
1374 * sliding down the snake. */
1375 if (left_section_len == right_section_len + 1) {
1376 if (!diff_state_add_chunk(state, true,
1377 left_atom, 1,
1378 right_atom, 0))
1379 goto return_rc;
1380 left_atom++;
1381 left_section_len--;
1382 } else if (right_section_len == left_section_len + 1) {
1383 if (!diff_state_add_chunk(state, true,
1384 left_atom, 0,
1385 right_atom, 1))
1386 goto return_rc;
1387 right_atom++;
1388 right_section_len--;
1389 } else if (left_section_len != right_section_len) {
1390 /* The numbers are making no sense. Should never
1391 * happen. */
1392 rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
1393 goto return_rc;
1394 }
1395
1396 if (!diff_state_add_chunk(state, true,
1397 left_atom, left_section_len,
1398 right_atom,
1399 right_section_len))
1400 goto return_rc;
1401 } else if (left_section_len && !right_section_len) {
1402 /* Only left atoms and none on the right, they form a
1403 * "minus" chunk, then. */
1404 if (!diff_state_add_chunk(state, true,
1405 left_atom, left_section_len,
1406 right_atom, 0))
1407 goto return_rc;
1408 } else if (!left_section_len && right_section_len) {
1409 /* No left atoms, only atoms on the right, they form a
1410 * "plus" chunk, then. */
1411 if (!diff_state_add_chunk(state, true,
1412 left_atom, 0,
1413 right_atom,
1414 right_section_len))
1415 goto return_rc;
1416 }
1417
1418 x = next_x;
1419 y = next_y;
1420 }
1421
1422 rc = DIFF_RC_OK;
1423
1424 return_rc:
1425 debug("** END %s rc=%d\n", __func__, rc);
1426 return rc;
1427 }
portable version of Game of Trees