##// END OF EJS Templates
test-ancestor: use random testing for missing ancestors...
Siddharth Agarwal -
r23331:3b1b8f25 default
parent child Browse files
Show More
@@ -1,4 +1,98 b''
1 1 from mercurial import ancestor, commands, hg, ui, util
2 from mercurial.node import nullrev
3 import binascii, getopt, math, os, random, sys, time
4
5 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):
6 '''nodes: total number of nodes in the graph
7 rootprob: probability that a new node (not 0) will be a root
8 mergeprob: probability that, excluding a root a node will be a merge
9 prevprob: probability that p1 will be the previous node
10
11 return value is a graph represented as an adjacency list.
12 '''
13 graph = [None] * nodes
14 for i in xrange(nodes):
15 if i == 0 or rng.random() < rootprob:
16 graph[i] = [nullrev]
17 elif i == 1:
18 graph[i] = [0]
19 elif rng.random() < mergeprob:
20 if i == 2 or rng.random() < prevprob:
21 # p1 is prev
22 p1 = i - 1
23 else:
24 p1 = rng.randrange(i - 1)
25 p2 = rng.choice(range(0, p1) + range(p1 + 1, i))
26 graph[i] = [p1, p2]
27 elif rng.random() < prevprob:
28 graph[i] = [i - 1]
29 else:
30 graph[i] = [rng.randrange(i - 1)]
31
32 return graph
33
34 def buildancestorsets(graph):
35 ancs = [None] * len(graph)
36 for i in xrange(len(graph)):
37 ancs[i] = set([i])
38 if graph[i] == [nullrev]:
39 continue
40 for p in graph[i]:
41 ancs[i].update(ancs[p])
42 return ancs
43
44 def naivemissingancestors(ancs, revs, bases):
45 res = set()
46 for rev in revs:
47 if rev != nullrev:
48 res.update(ancs[rev])
49 for base in bases:
50 if base != nullrev:
51 res.difference_update(ancs[base])
52 return sorted(res)
53
54 def test_missingancestors(seed, rng):
55 # empirically observed to take around 1 second
56 graphcount = 100
57 testcount = 100
58 nerrs = [0]
59 # the default mu and sigma give us a nice distribution of mostly
60 # single-digit counts (including 0) with some higher ones
61 def lognormrandom(mu, sigma):
62 return int(math.floor(rng.lognormvariate(mu, sigma)))
63
64 def samplerevs(nodes, mu=1.1, sigma=0.8):
65 count = min(lognormrandom(mu, sigma), len(nodes))
66 return rng.sample(nodes, count)
67
68 def err(seed, graph, bases, revs, output, expected):
69 if nerrs[0] == 0:
70 print >> sys.stderr, 'seed:', hex(seed)[:-1]
71 if gerrs[0] == 0:
72 print >> sys.stderr, 'graph:', graph
73 print >> sys.stderr, '* bases:', bases
74 print >> sys.stderr, '* revs: ', revs
75 print >> sys.stderr, '* output: ', output
76 print >> sys.stderr, '* expected:', expected
77 nerrs[0] += 1
78 gerrs[0] += 1
79
80 for g in xrange(graphcount):
81 graph = buildgraph(rng)
82 ancs = buildancestorsets(graph)
83 gerrs = [0]
84 for _ in xrange(testcount):
85 # start from nullrev to include it as a possibility
86 graphnodes = range(nullrev, len(graph))
87 bases = samplerevs(graphnodes)
88 revs = samplerevs(graphnodes)
89
90 # fast algorithm
91 h = ancestor.missingancestors(revs, bases, graph.__getitem__)
92 # reference slow algorithm
93 r = naivemissingancestors(ancs, revs, bases)
94 if h != r:
95 err(seed, graph, bases, revs, h, r)
2 96
3 97 # graph is a dict of child->parent adjacency lists for this graph:
4 98 # o 13
@@ -32,43 +126,6 b' from mercurial import ancestor, commands'
32 126 graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4],
33 127 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9],
34 128 13: [8]}
35 pfunc = graph.get
36
37 def runmissingancestors(revs, bases):
38 print "%% ancestors of %s and not of %s" % (revs, bases)
39 print ancestor.missingancestors(revs, bases, pfunc)
40
41 def test_missingancestors():
42 # Empty revs
43 runmissingancestors([], [1])
44 runmissingancestors([], [])
45
46 # If bases is empty, it's the same as if it were [nullrev]
47 runmissingancestors([12], [])
48
49 # Trivial case: revs == bases
50 runmissingancestors([0], [0])
51 runmissingancestors([4, 5, 6], [6, 5, 4])
52
53 # With nullrev
54 runmissingancestors([-1], [12])
55 runmissingancestors([12], [-1])
56
57 # 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an
58 # ancestor of 12 but not of 7.
59 runmissingancestors([12], [9])
60 runmissingancestors([9], [12])
61 runmissingancestors([12, 9], [7])
62 runmissingancestors([7, 6], [12])
63
64 # More complex cases
65 runmissingancestors([10], [11, 12])
66 runmissingancestors([11], [10])
67 runmissingancestors([11], [10, 12])
68 runmissingancestors([12], [10])
69 runmissingancestors([12], [11])
70 runmissingancestors([10, 11, 12], [13])
71 runmissingancestors([13], [10, 11, 12])
72 129
73 130 def genlazyancestors(revs, stoprev=0, inclusive=False):
74 131 print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
@@ -133,7 +190,20 b' def test_gca():'
133 190 print " Python returned: %s" % pygcas
134 191
135 192 def main():
136 test_missingancestors()
193 seed = None
194 opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed='])
195 for o, a in opts:
196 if o in ('-s', '--seed'):
197 seed = long(a, base=0) # accepts base 10 or 16 strings
198
199 if seed is None:
200 try:
201 seed = long(binascii.hexlify(os.urandom(16)), 16)
202 except AttributeError:
203 seed = long(time.time() * 1000)
204
205 rng = random.Random(seed)
206 test_missingancestors(seed, rng)
137 207 test_lazyancestors()
138 208 test_gca()
139 209
@@ -1,39 +1,3 b''
1 % ancestors of [] and not of [1]
2 []
3 % ancestors of [] and not of []
4 []
5 % ancestors of [12] and not of []
6 [0, 1, 2, 4, 6, 7, 9, 12]
7 % ancestors of [0] and not of [0]
8 []
9 % ancestors of [4, 5, 6] and not of [6, 5, 4]
10 []
11 % ancestors of [-1] and not of [12]
12 []
13 % ancestors of [12] and not of [-1]
14 [0, 1, 2, 4, 6, 7, 9, 12]
15 % ancestors of [12] and not of [9]
16 [12]
17 % ancestors of [9] and not of [12]
18 []
19 % ancestors of [12, 9] and not of [7]
20 [6, 9, 12]
21 % ancestors of [7, 6] and not of [12]
22 []
23 % ancestors of [10] and not of [11, 12]
24 [5, 10]
25 % ancestors of [11] and not of [10]
26 [3, 7, 11]
27 % ancestors of [11] and not of [10, 12]
28 [3, 11]
29 % ancestors of [12] and not of [10]
30 [6, 7, 9, 12]
31 % ancestors of [12] and not of [11]
32 [6, 9, 12]
33 % ancestors of [10, 11, 12] and not of [13]
34 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]
35 % ancestors of [13] and not of [10, 11, 12]
36 [8, 13]
37 1 % lazy ancestor set for [], stoprev = 0, inclusive = False
38 2 membership: []
39 3 iteration: []
General Comments 0
You need to be logged in to leave comments. Login now