Mercurial > hg
comparison mercurial/cext/revlog.c @ 33475:f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
find_deepest is used to find the "best" ancestors given a list. In the main
loop it keeps an invariant called 'ninteresting' which is supposed to contain
the number of non-zero entries in the 'interesting' array. This invariant is
incorrectly maintained, however, which leads the the algorithm returning an
empty result for certain graphs. This has been fixed.
Also, the 'interesting' array is supposed to fit 2^ancestors values, but is
incorrectly allocated to twice that size. This has been fixed as well.
The tests in test-ancestor.py compare the Python and C versions of the code,
and report the error correctly, since the Python version works correct. Even
so, I have added an additional test against the expected result, in the event
that both algorithms have an identical error in the future.
This fixes issue5623.
author | Sune Foldager <cryo@cyanite.org> |
---|---|
date | Fri, 14 Jul 2017 13:48:17 +0200 |
parents | f4f52bb362e6 |
children | 0f4ac3b6dee4 |
comparison
equal
deleted
inserted
replaced
33474:c514b4fb5e27 | 33475:f501322512b6 |
---|---|
1462 if (seen == NULL) { | 1462 if (seen == NULL) { |
1463 PyErr_NoMemory(); | 1463 PyErr_NoMemory(); |
1464 goto bail; | 1464 goto bail; |
1465 } | 1465 } |
1466 | 1466 |
1467 interesting = calloc(sizeof(*interesting), 2 << revcount); | 1467 interesting = calloc(sizeof(*interesting), 1 << revcount); |
1468 if (interesting == NULL) { | 1468 if (interesting == NULL) { |
1469 PyErr_NoMemory(); | 1469 PyErr_NoMemory(); |
1470 goto bail; | 1470 goto bail; |
1471 } | 1471 } |
1472 | 1472 |
1479 depth[n] = 1; | 1479 depth[n] = 1; |
1480 seen[n] = b; | 1480 seen[n] = b; |
1481 interesting[b] = 1; | 1481 interesting[b] = 1; |
1482 } | 1482 } |
1483 | 1483 |
1484 /* invariant: ninteresting is the number of non-zero entries in | |
1485 * interesting. */ | |
1484 ninteresting = (int)revcount; | 1486 ninteresting = (int)revcount; |
1485 | 1487 |
1486 for (v = maxrev; v >= 0 && ninteresting > 1; v--) { | 1488 for (v = maxrev; v >= 0 && ninteresting > 1; v--) { |
1487 int dv = depth[v]; | 1489 int dv = depth[v]; |
1488 int parents[2]; | 1490 int parents[2]; |
1521 long nsp = sp | sv; | 1523 long nsp = sp | sv; |
1522 if (nsp == sp) | 1524 if (nsp == sp) |
1523 continue; | 1525 continue; |
1524 seen[p] = nsp; | 1526 seen[p] = nsp; |
1525 interesting[sp] -= 1; | 1527 interesting[sp] -= 1; |
1526 if (interesting[sp] == 0 && interesting[nsp] > 0) | 1528 if (interesting[sp] == 0) |
1527 ninteresting -= 1; | 1529 ninteresting -= 1; |
1530 if (interesting[nsp] == 0) | |
1531 ninteresting += 1; | |
1528 interesting[nsp] += 1; | 1532 interesting[nsp] += 1; |
1529 } | 1533 } |
1530 } | 1534 } |
1531 interesting[sv] -= 1; | 1535 interesting[sv] -= 1; |
1532 if (interesting[sv] == 0) | 1536 if (interesting[sv] == 0) |