Show More
@@ -1,141 +1,211 b'' | |||||
1 | from mercurial import ancestor, commands, hg, ui, util |
|
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 | # graph is a dict of child->parent adjacency lists for this graph: |
|
97 | # graph is a dict of child->parent adjacency lists for this graph: | |
4 | # o 13 |
|
98 | # o 13 | |
5 | # | |
|
99 | # | | |
6 | # | o 12 |
|
100 | # | o 12 | |
7 | # | | |
|
101 | # | | | |
8 | # | | o 11 |
|
102 | # | | o 11 | |
9 | # | | |\ |
|
103 | # | | |\ | |
10 | # | | | | o 10 |
|
104 | # | | | | o 10 | |
11 | # | | | | | |
|
105 | # | | | | | | |
12 | # | o---+ | 9 |
|
106 | # | o---+ | 9 | |
13 | # | | | | | |
|
107 | # | | | | | | |
14 | # o | | | | 8 |
|
108 | # o | | | | 8 | |
15 | # / / / / |
|
109 | # / / / / | |
16 | # | | o | 7 |
|
110 | # | | o | 7 | |
17 | # | | | | |
|
111 | # | | | | | |
18 | # o---+ | 6 |
|
112 | # o---+ | 6 | |
19 | # / / / |
|
113 | # / / / | |
20 | # | | o 5 |
|
114 | # | | o 5 | |
21 | # | |/ |
|
115 | # | |/ | |
22 | # | o 4 |
|
116 | # | o 4 | |
23 | # | | |
|
117 | # | | | |
24 | # o | 3 |
|
118 | # o | 3 | |
25 | # | | |
|
119 | # | | | |
26 | # | o 2 |
|
120 | # | o 2 | |
27 | # |/ |
|
121 | # |/ | |
28 | # o 1 |
|
122 | # o 1 | |
29 | # | |
|
123 | # | | |
30 | # o 0 |
|
124 | # o 0 | |
31 |
|
125 | |||
32 | graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], |
|
126 | graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | |
33 | 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], |
|
127 | 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | |
34 | 13: [8]} |
|
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 | def genlazyancestors(revs, stoprev=0, inclusive=False): |
|
130 | def genlazyancestors(revs, stoprev=0, inclusive=False): | |
74 | print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" % |
|
131 | print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" % | |
75 | (revs, stoprev, inclusive)) |
|
132 | (revs, stoprev, inclusive)) | |
76 | return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev, |
|
133 | return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev, | |
77 | inclusive=inclusive) |
|
134 | inclusive=inclusive) | |
78 |
|
135 | |||
79 | def printlazyancestors(s, l): |
|
136 | def printlazyancestors(s, l): | |
80 | print 'membership: %r' % [n for n in l if n in s] |
|
137 | print 'membership: %r' % [n for n in l if n in s] | |
81 | print 'iteration: %r' % list(s) |
|
138 | print 'iteration: %r' % list(s) | |
82 |
|
139 | |||
83 | def test_lazyancestors(): |
|
140 | def test_lazyancestors(): | |
84 | # Empty revs |
|
141 | # Empty revs | |
85 | s = genlazyancestors([]) |
|
142 | s = genlazyancestors([]) | |
86 | printlazyancestors(s, [3, 0, -1]) |
|
143 | printlazyancestors(s, [3, 0, -1]) | |
87 |
|
144 | |||
88 | # Standard example |
|
145 | # Standard example | |
89 | s = genlazyancestors([11, 13]) |
|
146 | s = genlazyancestors([11, 13]) | |
90 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
147 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
91 |
|
148 | |||
92 | # Standard with ancestry in the initial set (1 is ancestor of 3) |
|
149 | # Standard with ancestry in the initial set (1 is ancestor of 3) | |
93 | s = genlazyancestors([1, 3]) |
|
150 | s = genlazyancestors([1, 3]) | |
94 | printlazyancestors(s, [1, -1, 0]) |
|
151 | printlazyancestors(s, [1, -1, 0]) | |
95 |
|
152 | |||
96 | # Including revs |
|
153 | # Including revs | |
97 | s = genlazyancestors([11, 13], inclusive=True) |
|
154 | s = genlazyancestors([11, 13], inclusive=True) | |
98 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
155 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
99 |
|
156 | |||
100 | # Test with stoprev |
|
157 | # Test with stoprev | |
101 | s = genlazyancestors([11, 13], stoprev=6) |
|
158 | s = genlazyancestors([11, 13], stoprev=6) | |
102 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
159 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
103 | s = genlazyancestors([11, 13], stoprev=6, inclusive=True) |
|
160 | s = genlazyancestors([11, 13], stoprev=6, inclusive=True) | |
104 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
161 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
105 |
|
162 | |||
106 |
|
163 | |||
107 | # The C gca algorithm requires a real repo. These are textual descriptions of |
|
164 | # The C gca algorithm requires a real repo. These are textual descriptions of | |
108 | # DAGs that have been known to be problematic. |
|
165 | # DAGs that have been known to be problematic. | |
109 | dagtests = [ |
|
166 | dagtests = [ | |
110 | '+2*2*2/*3/2', |
|
167 | '+2*2*2/*3/2', | |
111 | '+3*3/*2*2/*4*4/*4/2*4/2*2', |
|
168 | '+3*3/*2*2/*4*4/*4/2*4/2*2', | |
112 | ] |
|
169 | ] | |
113 | def test_gca(): |
|
170 | def test_gca(): | |
114 | u = ui.ui() |
|
171 | u = ui.ui() | |
115 | for i, dag in enumerate(dagtests): |
|
172 | for i, dag in enumerate(dagtests): | |
116 | repo = hg.repository(u, 'gca%d' % i, create=1) |
|
173 | repo = hg.repository(u, 'gca%d' % i, create=1) | |
117 | cl = repo.changelog |
|
174 | cl = repo.changelog | |
118 | if not util.safehasattr(cl.index, 'ancestors'): |
|
175 | if not util.safehasattr(cl.index, 'ancestors'): | |
119 | # C version not available |
|
176 | # C version not available | |
120 | return |
|
177 | return | |
121 |
|
178 | |||
122 | commands.debugbuilddag(u, repo, dag) |
|
179 | commands.debugbuilddag(u, repo, dag) | |
123 | # Compare the results of the Python and C versions. This does not |
|
180 | # Compare the results of the Python and C versions. This does not | |
124 | # include choosing a winner when more than one gca exists -- we make |
|
181 | # include choosing a winner when more than one gca exists -- we make | |
125 | # sure both return exactly the same set of gcas. |
|
182 | # sure both return exactly the same set of gcas. | |
126 | for a in cl: |
|
183 | for a in cl: | |
127 | for b in cl: |
|
184 | for b in cl: | |
128 | cgcas = sorted(cl.index.ancestors(a, b)) |
|
185 | cgcas = sorted(cl.index.ancestors(a, b)) | |
129 | pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) |
|
186 | pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) | |
130 | if cgcas != pygcas: |
|
187 | if cgcas != pygcas: | |
131 | print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b) |
|
188 | print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b) | |
132 | print " C returned: %s" % cgcas |
|
189 | print " C returned: %s" % cgcas | |
133 | print " Python returned: %s" % pygcas |
|
190 | print " Python returned: %s" % pygcas | |
134 |
|
191 | |||
135 | def main(): |
|
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 | test_lazyancestors() |
|
207 | test_lazyancestors() | |
138 | test_gca() |
|
208 | test_gca() | |
139 |
|
209 | |||
140 | if __name__ == '__main__': |
|
210 | if __name__ == '__main__': | |
141 | main() |
|
211 | main() |
@@ -1,54 +1,18 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 | % lazy ancestor set for [], stoprev = 0, inclusive = False |
|
1 | % lazy ancestor set for [], stoprev = 0, inclusive = False | |
38 | membership: [] |
|
2 | membership: [] | |
39 | iteration: [] |
|
3 | iteration: [] | |
40 | % lazy ancestor set for [11, 13], stoprev = 0, inclusive = False |
|
4 | % lazy ancestor set for [11, 13], stoprev = 0, inclusive = False | |
41 | membership: [7, 8, 3, 4, 1, 0] |
|
5 | membership: [7, 8, 3, 4, 1, 0] | |
42 | iteration: [3, 7, 8, 1, 4, 0, 2] |
|
6 | iteration: [3, 7, 8, 1, 4, 0, 2] | |
43 | % lazy ancestor set for [1, 3], stoprev = 0, inclusive = False |
|
7 | % lazy ancestor set for [1, 3], stoprev = 0, inclusive = False | |
44 | membership: [1, 0] |
|
8 | membership: [1, 0] | |
45 | iteration: [0, 1] |
|
9 | iteration: [0, 1] | |
46 | % lazy ancestor set for [11, 13], stoprev = 0, inclusive = True |
|
10 | % lazy ancestor set for [11, 13], stoprev = 0, inclusive = True | |
47 | membership: [11, 13, 7, 8, 3, 4, 1, 0] |
|
11 | membership: [11, 13, 7, 8, 3, 4, 1, 0] | |
48 | iteration: [11, 13, 3, 7, 8, 1, 4, 0, 2] |
|
12 | iteration: [11, 13, 3, 7, 8, 1, 4, 0, 2] | |
49 | % lazy ancestor set for [11, 13], stoprev = 6, inclusive = False |
|
13 | % lazy ancestor set for [11, 13], stoprev = 6, inclusive = False | |
50 | membership: [7, 8] |
|
14 | membership: [7, 8] | |
51 | iteration: [7, 8] |
|
15 | iteration: [7, 8] | |
52 | % lazy ancestor set for [11, 13], stoprev = 6, inclusive = True |
|
16 | % lazy ancestor set for [11, 13], stoprev = 6, inclusive = True | |
53 | membership: [11, 13, 7, 8] |
|
17 | membership: [11, 13, 7, 8] | |
54 | iteration: [11, 13, 7, 8] |
|
18 | iteration: [11, 13, 7, 8] |
General Comments 0
You need to be logged in to leave comments.
Login now