--- a/tests/test-ancestor.py Sat Oct 05 10:29:34 2019 -0400
+++ b/tests/test-ancestor.py Sun Oct 06 09:45:02 2019 -0400
@@ -22,6 +22,7 @@
long = int
xrange = range
+
def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):
'''nodes: total number of nodes in the graph
rootprob: probability that a new node (not 0) will be a root
@@ -51,6 +52,7 @@
return graph
+
def buildancestorsets(graph):
ancs = [None] * len(graph)
for i in xrange(len(graph)):
@@ -61,17 +63,21 @@
ancs[i].update(ancs[p])
return ancs
+
class naiveincrementalmissingancestors(object):
def __init__(self, ancs, bases):
self.ancs = ancs
self.bases = set(bases)
+
def addbases(self, newbases):
self.bases.update(newbases)
+
def removeancestorsfrom(self, revs):
for base in self.bases:
if base != nullrev:
revs.difference_update(self.ancs[base])
revs.discard(nullrev)
+
def missingancestors(self, revs):
res = set()
for rev in revs:
@@ -82,6 +88,7 @@
res.difference_update(self.ancs[base])
return sorted(res)
+
def test_missingancestors(seed, rng):
# empirically observed to take around 1 second
graphcount = 100
@@ -138,8 +145,14 @@
inc.removeancestorsfrom(hrevs)
naiveinc.removeancestorsfrom(rrevs)
if hrevs != rrevs:
- err(seed, graph, bases, seq, sorted(hrevs),
- sorted(rrevs))
+ err(
+ seed,
+ graph,
+ bases,
+ seq,
+ sorted(hrevs),
+ sorted(rrevs),
+ )
else:
revs = samplerevs(graphnodes)
seq.append(('missingancestors', revs))
@@ -148,6 +161,7 @@
if h != r:
err(seed, graph, bases, seq, h, r)
+
# graph is a dict of child->parent adjacency lists for this graph:
# o 13
# |
@@ -177,9 +191,23 @@
# |
# o 0
-graph = {0: [-1, -1], 1: [0, -1], 2: [1, -1], 3: [1, -1], 4: [2, -1],
- 5: [4, -1], 6: [4, -1], 7: [4, -1], 8: [-1, -1], 9: [6, 7],
- 10: [5, -1], 11: [3, 7], 12: [9, -1], 13: [8, -1]}
+graph = {
+ 0: [-1, -1],
+ 1: [0, -1],
+ 2: [1, -1],
+ 3: [1, -1],
+ 4: [2, -1],
+ 5: [4, -1],
+ 6: [4, -1],
+ 7: [4, -1],
+ 8: [-1, -1],
+ 9: [6, 7],
+ 10: [5, -1],
+ 11: [3, 7],
+ 12: [9, -1],
+ 13: [8, -1],
+}
+
def test_missingancestors_explicit():
"""A few explicit cases, easier to check for catching errors in refactors.
@@ -187,43 +215,128 @@
The bigger graph at the end has been produced by the random generator
above, and we have some evidence that the other tests don't cover it.
"""
- for i, (bases, revs) in enumerate((({1, 2, 3, 4, 7}, set(xrange(10))),
- ({10}, set({11, 12, 13, 14})),
- ({7}, set({1, 2, 3, 4, 5})),
- )):
+ for i, (bases, revs) in enumerate(
+ (
+ ({1, 2, 3, 4, 7}, set(xrange(10))),
+ ({10}, set({11, 12, 13, 14})),
+ ({7}, set({1, 2, 3, 4, 5})),
+ )
+ ):
print("%% removeancestorsfrom(), example %d" % (i + 1))
missanc = ancestor.incrementalmissingancestors(graph.get, bases)
missanc.removeancestorsfrom(revs)
print("remaining (sorted): %s" % sorted(list(revs)))
- for i, (bases, revs) in enumerate((({10}, {11}),
- ({11}, {10}),
- ({7}, {9, 11}),
- )):
+ for i, (bases, revs) in enumerate(
+ (({10}, {11}), ({11}, {10}), ({7}, {9, 11}),)
+ ):
print("%% missingancestors(), example %d" % (i + 1))
missanc = ancestor.incrementalmissingancestors(graph.get, bases)
print("return %s" % missanc.missingancestors(revs))
print("% removeancestorsfrom(), bigger graph")
vecgraph = [
- [-1, -1], [0, -1], [1, 0], [2, 1], [3, -1], [4, -1], [5, 1],
- [2, -1], [7, -1], [8, -1], [9, -1], [10, 1], [3, -1], [12, -1],
- [13, -1], [14, -1], [4, -1], [16, -1], [17, -1], [18, -1],
- [19, 11], [20, -1], [21, -1], [22, -1], [23, -1], [2, -1],
- [3, -1], [26, 24], [27, -1], [28, -1], [12, -1], [1, -1], [1, 9],
- [32, -1], [33, -1], [34, 31], [35, -1], [36, 26], [37, -1],
- [38, -1], [39, -1], [40, -1], [41, -1], [42, 26], [0, -1],
- [44, -1], [45, 4], [40, -1], [47, -1], [36, 0], [49, -1],
- [-1, -1], [51, -1], [52, -1], [53, -1], [14, -1],
- [55, -1], [15, -1], [23, -1], [58, -1], [59, -1], [2, -1],
- [61, 59], [62, -1], [63, -1], [-1, -1], [65, -1],
- [66, -1], [67, -1], [68, -1], [37, 28], [69, 25],
- [71, -1], [72, -1], [50, 2], [74, -1], [12, -1],
- [18, -1], [77, -1], [78, -1], [79, -1], [43, 33],
- [81, -1], [82, -1], [83, -1], [84, 45], [85, -1],
- [86, -1], [-1, -1], [88, -1], [-1, -1], [76, 83], [44, -1],
- [92, -1], [93, -1], [9, -1], [95, 67], [96, -1], [97, -1],
- [-1, -1]]
+ [-1, -1],
+ [0, -1],
+ [1, 0],
+ [2, 1],
+ [3, -1],
+ [4, -1],
+ [5, 1],
+ [2, -1],
+ [7, -1],
+ [8, -1],
+ [9, -1],
+ [10, 1],
+ [3, -1],
+ [12, -1],
+ [13, -1],
+ [14, -1],
+ [4, -1],
+ [16, -1],
+ [17, -1],
+ [18, -1],
+ [19, 11],
+ [20, -1],
+ [21, -1],
+ [22, -1],
+ [23, -1],
+ [2, -1],
+ [3, -1],
+ [26, 24],
+ [27, -1],
+ [28, -1],
+ [12, -1],
+ [1, -1],
+ [1, 9],
+ [32, -1],
+ [33, -1],
+ [34, 31],
+ [35, -1],
+ [36, 26],
+ [37, -1],
+ [38, -1],
+ [39, -1],
+ [40, -1],
+ [41, -1],
+ [42, 26],
+ [0, -1],
+ [44, -1],
+ [45, 4],
+ [40, -1],
+ [47, -1],
+ [36, 0],
+ [49, -1],
+ [-1, -1],
+ [51, -1],
+ [52, -1],
+ [53, -1],
+ [14, -1],
+ [55, -1],
+ [15, -1],
+ [23, -1],
+ [58, -1],
+ [59, -1],
+ [2, -1],
+ [61, 59],
+ [62, -1],
+ [63, -1],
+ [-1, -1],
+ [65, -1],
+ [66, -1],
+ [67, -1],
+ [68, -1],
+ [37, 28],
+ [69, 25],
+ [71, -1],
+ [72, -1],
+ [50, 2],
+ [74, -1],
+ [12, -1],
+ [18, -1],
+ [77, -1],
+ [78, -1],
+ [79, -1],
+ [43, 33],
+ [81, -1],
+ [82, -1],
+ [83, -1],
+ [84, 45],
+ [85, -1],
+ [86, -1],
+ [-1, -1],
+ [88, -1],
+ [-1, -1],
+ [76, 83],
+ [44, -1],
+ [92, -1],
+ [93, -1],
+ [9, -1],
+ [95, 67],
+ [96, -1],
+ [97, -1],
+ [-1, -1],
+ ]
problem_rev = 28
problem_base = 70
# problem_rev is a parent of problem_base, but a faulty implementation
@@ -239,16 +352,24 @@
else:
print("Ok")
+
def genlazyancestors(revs, stoprev=0, inclusive=False):
- print(("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
- (revs, stoprev, inclusive)))
- return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev,
- inclusive=inclusive)
+ print(
+ (
+ "%% lazy ancestor set for %s, stoprev = %s, inclusive = %s"
+ % (revs, stoprev, inclusive)
+ )
+ )
+ return ancestor.lazyancestors(
+ graph.get, revs, stoprev=stoprev, inclusive=inclusive
+ )
+
def printlazyancestors(s, l):
print('membership: %r' % [n for n in l if n in s])
print('iteration: %r' % list(s))
+
def test_lazyancestors():
# Empty revs
s = genlazyancestors([])
@@ -282,6 +403,7 @@
s = genlazyancestors([10, 1], inclusive=True)
printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1])
+
# The C gca algorithm requires a real repo. These are textual descriptions of
# DAGs that have been known to be problematic, and, optionally, known pairs
# of revisions and their expected ancestor list.
@@ -290,6 +412,8 @@
(b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}),
(b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}),
]
+
+
def test_gca():
u = uimod.ui.load()
for i, (dag, tests) in enumerate(dagtests):
@@ -312,19 +436,21 @@
if (a, b) in tests:
expected = tests[(a, b)]
if cgcas != pygcas or (expected and cgcas != expected):
- print("test_gca: for dag %s, gcas for %d, %d:"
- % (dag, a, b))
+ print(
+ "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b)
+ )
print(" C returned: %s" % cgcas)
print(" Python returned: %s" % pygcas)
if expected:
print(" expected: %s" % expected)
+
def main():
seed = None
opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed='])
for o, a in opts:
if o in ('-s', '--seed'):
- seed = long(a, base=0) # accepts base 10 or 16 strings
+ seed = long(a, base=0) # accepts base 10 or 16 strings
if seed is None:
try:
@@ -338,5 +464,6 @@
test_lazyancestors()
test_gca()
+
if __name__ == '__main__':
main()