Show More
@@ -1,138 +1,141 | |||||
1 | from mercurial import ancestor, commands, hg, ui, util |
|
1 | from mercurial import ancestor, commands, hg, ui, util | |
2 |
|
2 | |||
3 | # graph is a dict of child->parent adjacency lists for this graph: |
|
3 | # graph is a dict of child->parent adjacency lists for this graph: | |
4 | # o 13 |
|
4 | # o 13 | |
5 | # | |
|
5 | # | | |
6 | # | o 12 |
|
6 | # | o 12 | |
7 | # | | |
|
7 | # | | | |
8 | # | | o 11 |
|
8 | # | | o 11 | |
9 | # | | |\ |
|
9 | # | | |\ | |
10 | # | | | | o 10 |
|
10 | # | | | | o 10 | |
11 | # | | | | | |
|
11 | # | | | | | | |
12 | # | o---+ | 9 |
|
12 | # | o---+ | 9 | |
13 | # | | | | | |
|
13 | # | | | | | | |
14 | # o | | | | 8 |
|
14 | # o | | | | 8 | |
15 | # / / / / |
|
15 | # / / / / | |
16 | # | | o | 7 |
|
16 | # | | o | 7 | |
17 | # | | | | |
|
17 | # | | | | | |
18 | # o---+ | 6 |
|
18 | # o---+ | 6 | |
19 | # / / / |
|
19 | # / / / | |
20 | # | | o 5 |
|
20 | # | | o 5 | |
21 | # | |/ |
|
21 | # | |/ | |
22 | # | o 4 |
|
22 | # | o 4 | |
23 | # | | |
|
23 | # | | | |
24 | # o | 3 |
|
24 | # o | 3 | |
25 | # | | |
|
25 | # | | | |
26 | # | o 2 |
|
26 | # | o 2 | |
27 | # |/ |
|
27 | # |/ | |
28 | # o 1 |
|
28 | # o 1 | |
29 | # | |
|
29 | # | | |
30 | # o 0 |
|
30 | # o 0 | |
31 |
|
31 | |||
32 | graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], |
|
32 | 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], |
|
33 | 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | |
34 | 13: [8]} |
|
34 | 13: [8]} | |
35 | pfunc = graph.get |
|
35 | pfunc = graph.get | |
36 |
|
36 | |||
37 | def runmissingancestors(revs, bases): |
|
37 | def runmissingancestors(revs, bases): | |
38 | print "%% ancestors of %s and not of %s" % (revs, bases) |
|
38 | print "%% ancestors of %s and not of %s" % (revs, bases) | |
39 | print ancestor.missingancestors(revs, bases, pfunc) |
|
39 | print ancestor.missingancestors(revs, bases, pfunc) | |
40 |
|
40 | |||
41 | def test_missingancestors(): |
|
41 | def test_missingancestors(): | |
42 | # Empty revs |
|
42 | # Empty revs | |
43 | runmissingancestors([], [1]) |
|
43 | runmissingancestors([], [1]) | |
44 | runmissingancestors([], []) |
|
44 | runmissingancestors([], []) | |
45 |
|
45 | |||
46 | # If bases is empty, it's the same as if it were [nullrev] |
|
46 | # If bases is empty, it's the same as if it were [nullrev] | |
47 | runmissingancestors([12], []) |
|
47 | runmissingancestors([12], []) | |
48 |
|
48 | |||
49 | # Trivial case: revs == bases |
|
49 | # Trivial case: revs == bases | |
50 | runmissingancestors([0], [0]) |
|
50 | runmissingancestors([0], [0]) | |
51 | runmissingancestors([4, 5, 6], [6, 5, 4]) |
|
51 | runmissingancestors([4, 5, 6], [6, 5, 4]) | |
52 |
|
52 | |||
53 | # With nullrev |
|
53 | # With nullrev | |
54 | runmissingancestors([-1], [12]) |
|
54 | runmissingancestors([-1], [12]) | |
55 | runmissingancestors([12], [-1]) |
|
55 | runmissingancestors([12], [-1]) | |
56 |
|
56 | |||
57 | # 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an |
|
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. |
|
58 | # ancestor of 12 but not of 7. | |
59 | runmissingancestors([12], [9]) |
|
59 | runmissingancestors([12], [9]) | |
60 | runmissingancestors([9], [12]) |
|
60 | runmissingancestors([9], [12]) | |
61 | runmissingancestors([12, 9], [7]) |
|
61 | runmissingancestors([12, 9], [7]) | |
62 | runmissingancestors([7, 6], [12]) |
|
62 | runmissingancestors([7, 6], [12]) | |
63 |
|
63 | |||
64 | # More complex cases |
|
64 | # More complex cases | |
65 | runmissingancestors([10], [11, 12]) |
|
65 | runmissingancestors([10], [11, 12]) | |
66 | runmissingancestors([11], [10]) |
|
66 | runmissingancestors([11], [10]) | |
67 | runmissingancestors([11], [10, 12]) |
|
67 | runmissingancestors([11], [10, 12]) | |
68 | runmissingancestors([12], [10]) |
|
68 | runmissingancestors([12], [10]) | |
69 | runmissingancestors([12], [11]) |
|
69 | runmissingancestors([12], [11]) | |
70 | runmissingancestors([10, 11, 12], [13]) |
|
70 | runmissingancestors([10, 11, 12], [13]) | |
71 | runmissingancestors([13], [10, 11, 12]) |
|
71 | runmissingancestors([13], [10, 11, 12]) | |
72 |
|
72 | |||
73 | def genlazyancestors(revs, stoprev=0, inclusive=False): |
|
73 | def genlazyancestors(revs, stoprev=0, inclusive=False): | |
74 | print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" % |
|
74 | print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" % | |
75 | (revs, stoprev, inclusive)) |
|
75 | (revs, stoprev, inclusive)) | |
76 | return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev, |
|
76 | return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev, | |
77 | inclusive=inclusive) |
|
77 | inclusive=inclusive) | |
78 |
|
78 | |||
79 | def printlazyancestors(s, l): |
|
79 | def printlazyancestors(s, l): | |
80 | print 'membership: %r' % [n for n in l if n in s] |
|
80 | print 'membership: %r' % [n for n in l if n in s] | |
81 | print 'iteration: %r' % list(s) |
|
81 | print 'iteration: %r' % list(s) | |
82 |
|
82 | |||
83 | def test_lazyancestors(): |
|
83 | def test_lazyancestors(): | |
84 | # Empty revs |
|
84 | # Empty revs | |
85 | s = genlazyancestors([]) |
|
85 | s = genlazyancestors([]) | |
86 | printlazyancestors(s, [3, 0, -1]) |
|
86 | printlazyancestors(s, [3, 0, -1]) | |
87 |
|
87 | |||
88 | # Standard example |
|
88 | # Standard example | |
89 | s = genlazyancestors([11, 13]) |
|
89 | s = genlazyancestors([11, 13]) | |
90 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
90 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
91 |
|
91 | |||
92 | # Standard with ancestry in the initial set (1 is ancestor of 3) |
|
92 | # Standard with ancestry in the initial set (1 is ancestor of 3) | |
93 | s = genlazyancestors([1, 3]) |
|
93 | s = genlazyancestors([1, 3]) | |
94 | printlazyancestors(s, [1, -1, 0]) |
|
94 | printlazyancestors(s, [1, -1, 0]) | |
95 |
|
95 | |||
96 | # Including revs |
|
96 | # Including revs | |
97 | s = genlazyancestors([11, 13], inclusive=True) |
|
97 | s = genlazyancestors([11, 13], inclusive=True) | |
98 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
98 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
99 |
|
99 | |||
100 | # Test with stoprev |
|
100 | # Test with stoprev | |
101 | s = genlazyancestors([11, 13], stoprev=6) |
|
101 | s = genlazyancestors([11, 13], stoprev=6) | |
102 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
102 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
103 | s = genlazyancestors([11, 13], stoprev=6, inclusive=True) |
|
103 | s = genlazyancestors([11, 13], stoprev=6, inclusive=True) | |
104 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
|
104 | printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | |
105 |
|
105 | |||
106 |
|
106 | |||
107 | # The C gca algorithm requires a real repo. These are textual descriptions of |
|
107 | # The C gca algorithm requires a real repo. These are textual descriptions of | |
108 | # DAGs that have been known to be problematic. |
|
108 | # DAGs that have been known to be problematic. | |
109 | dagtests = [ |
|
109 | dagtests = [ | |
110 | '+2*2*2/*3/2', |
|
110 | '+2*2*2/*3/2', | |
111 | '+3*3/*2*2/*4*4/*4/2*4/2*2', |
|
111 | '+3*3/*2*2/*4*4/*4/2*4/2*2', | |
112 | ] |
|
112 | ] | |
113 | def test_gca(): |
|
113 | def test_gca(): | |
114 | u = ui.ui() |
|
114 | u = ui.ui() | |
115 | for i, dag in enumerate(dagtests): |
|
115 | for i, dag in enumerate(dagtests): | |
116 | repo = hg.repository(u, 'gca%d' % i, create=1) |
|
116 | repo = hg.repository(u, 'gca%d' % i, create=1) | |
117 | cl = repo.changelog |
|
117 | cl = repo.changelog | |
118 | if not util.safehasattr(cl.index, 'ancestors'): |
|
118 | if not util.safehasattr(cl.index, 'ancestors'): | |
119 | # C version not available |
|
119 | # C version not available | |
120 | return |
|
120 | return | |
121 |
|
121 | |||
122 | commands.debugbuilddag(u, repo, dag) |
|
122 | commands.debugbuilddag(u, repo, dag) | |
123 | # Compare the results of the Python and C versions. This does not |
|
123 | # 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 |
|
124 | # include choosing a winner when more than one gca exists -- we make | |
125 | # sure both return exactly the same set of gcas. |
|
125 | # sure both return exactly the same set of gcas. | |
126 | for a in cl: |
|
126 | for a in cl: | |
127 | for b in cl: |
|
127 | for b in cl: | |
128 | cgcas = sorted(cl.index.ancestors(a, b)) |
|
128 | cgcas = sorted(cl.index.ancestors(a, b)) | |
129 | pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) |
|
129 | pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) | |
130 | if cgcas != pygcas: |
|
130 | if cgcas != pygcas: | |
131 | print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b) |
|
131 | print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b) | |
132 | print " C returned: %s" % cgcas |
|
132 | print " C returned: %s" % cgcas | |
133 | print " Python returned: %s" % pygcas |
|
133 | print " Python returned: %s" % pygcas | |
134 |
|
134 | |||
135 | if __name__ == '__main__': |
|
135 | def main(): | |
136 | test_missingancestors() |
|
136 | test_missingancestors() | |
137 | test_lazyancestors() |
|
137 | test_lazyancestors() | |
138 | test_gca() |
|
138 | test_gca() | |
|
139 | ||||
|
140 | if __name__ == '__main__': | |||
|
141 | main() |
General Comments 0
You need to be logged in to leave comments.
Login now