Show More
@@ -0,0 +1,74 b'' | |||
|
1 | from mercurial import ancestor | |
|
2 | ||
|
3 | # graph is a dict of child->parent adjacency lists for this graph: | |
|
4 | # o 13 | |
|
5 | # | | |
|
6 | # | o 12 | |
|
7 | # | | | |
|
8 | # | | o 11 | |
|
9 | # | | |\ | |
|
10 | # | | | | o 10 | |
|
11 | # | | | | | | |
|
12 | # | o---+ | 9 | |
|
13 | # | | | | | | |
|
14 | # o | | | | 8 | |
|
15 | # / / / / | |
|
16 | # | | o | 7 | |
|
17 | # | | | | | |
|
18 | # o---+ | 6 | |
|
19 | # / / / | |
|
20 | # | | o 5 | |
|
21 | # | |/ | |
|
22 | # | o 4 | |
|
23 | # | | | |
|
24 | # o | 3 | |
|
25 | # | | | |
|
26 | # | o 2 | |
|
27 | # |/ | |
|
28 | # o 1 | |
|
29 | # | | |
|
30 | # o 0 | |
|
31 | ||
|
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], | |
|
34 | 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 | ||
|
73 | if __name__ == '__main__': | |
|
74 | test_missingancestors() |
@@ -0,0 +1,36 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] |
@@ -101,88 +101,6 b' def missingancestors(revs, bases, pfunc)' | |||
|
101 | 101 | |
|
102 | 102 | revs and bases should both be iterables. pfunc must return a list of |
|
103 | 103 | parent revs for a given revs. |
|
104 | ||
|
105 | graph is a dict of child->parent adjacency lists for this graph: | |
|
106 | o 13 | |
|
107 | | | |
|
108 | | o 12 | |
|
109 | | | | |
|
110 | | | o 11 | |
|
111 | | | |\ | |
|
112 | | | | | o 10 | |
|
113 | | | | | | | |
|
114 | | o---+ | 9 | |
|
115 | | | | | | | |
|
116 | o | | | | 8 | |
|
117 | / / / / | |
|
118 | | | o | 7 | |
|
119 | | | | | | |
|
120 | o---+ | 6 | |
|
121 | / / / | |
|
122 | | | o 5 | |
|
123 | | |/ | |
|
124 | | o 4 | |
|
125 | | | | |
|
126 | o | 3 | |
|
127 | | | | |
|
128 | | o 2 | |
|
129 | |/ | |
|
130 | o 1 | |
|
131 | | | |
|
132 | o 0 | |
|
133 | >>> graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | |
|
134 | ... 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | |
|
135 | ... 13: [8]} | |
|
136 | >>> pfunc = graph.get | |
|
137 | ||
|
138 | Empty revs | |
|
139 | >>> missingancestors([], [1], pfunc) | |
|
140 | [] | |
|
141 | >>> missingancestors([], [], pfunc) | |
|
142 | [] | |
|
143 | ||
|
144 | If bases is empty, it's the same as if it were [nullrev] | |
|
145 | >>> missingancestors([12], [], pfunc) | |
|
146 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
147 | ||
|
148 | Trivial case: revs == bases | |
|
149 | >>> missingancestors([0], [0], pfunc) | |
|
150 | [] | |
|
151 | >>> missingancestors([4, 5, 6], [6, 5, 4], pfunc) | |
|
152 | [] | |
|
153 | ||
|
154 | With nullrev | |
|
155 | >>> missingancestors([-1], [12], pfunc) | |
|
156 | [] | |
|
157 | >>> missingancestors([12], [-1], pfunc) | |
|
158 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
159 | ||
|
160 | 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an | |
|
161 | ancestor of 12 but not of 7. | |
|
162 | >>> missingancestors([12], [9], pfunc) | |
|
163 | [12] | |
|
164 | >>> missingancestors([9], [12], pfunc) | |
|
165 | [] | |
|
166 | >>> missingancestors([12, 9], [7], pfunc) | |
|
167 | [6, 9, 12] | |
|
168 | >>> missingancestors([7, 6], [12], pfunc) | |
|
169 | [] | |
|
170 | ||
|
171 | More complex cases | |
|
172 | >>> missingancestors([10], [11, 12], pfunc) | |
|
173 | [5, 10] | |
|
174 | >>> missingancestors([11], [10], pfunc) | |
|
175 | [3, 7, 11] | |
|
176 | >>> missingancestors([11], [10, 12], pfunc) | |
|
177 | [3, 11] | |
|
178 | >>> missingancestors([12], [10], pfunc) | |
|
179 | [6, 7, 9, 12] | |
|
180 | >>> missingancestors([12], [11], pfunc) | |
|
181 | [6, 9, 12] | |
|
182 | >>> missingancestors([10, 11, 12], [13], pfunc) | |
|
183 | [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12] | |
|
184 | >>> missingancestors([13], [10, 11, 12], pfunc) | |
|
185 | [8, 13] | |
|
186 | 104 | """ |
|
187 | 105 | |
|
188 | 106 | revsvisit = set(revs) |
General Comments 0
You need to be logged in to leave comments.
Login now