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