49 else: |
50 else: |
50 graph[i] = [rng.randrange(i - 1)] |
51 graph[i] = [rng.randrange(i - 1)] |
51 |
52 |
52 return graph |
53 return graph |
53 |
54 |
|
55 |
54 def buildancestorsets(graph): |
56 def buildancestorsets(graph): |
55 ancs = [None] * len(graph) |
57 ancs = [None] * len(graph) |
56 for i in xrange(len(graph)): |
58 for i in xrange(len(graph)): |
57 ancs[i] = {i} |
59 ancs[i] = {i} |
58 if graph[i] == [nullrev]: |
60 if graph[i] == [nullrev]: |
59 continue |
61 continue |
60 for p in graph[i]: |
62 for p in graph[i]: |
61 ancs[i].update(ancs[p]) |
63 ancs[i].update(ancs[p]) |
62 return ancs |
64 return ancs |
63 |
65 |
|
66 |
64 class naiveincrementalmissingancestors(object): |
67 class naiveincrementalmissingancestors(object): |
65 def __init__(self, ancs, bases): |
68 def __init__(self, ancs, bases): |
66 self.ancs = ancs |
69 self.ancs = ancs |
67 self.bases = set(bases) |
70 self.bases = set(bases) |
|
71 |
68 def addbases(self, newbases): |
72 def addbases(self, newbases): |
69 self.bases.update(newbases) |
73 self.bases.update(newbases) |
|
74 |
70 def removeancestorsfrom(self, revs): |
75 def removeancestorsfrom(self, revs): |
71 for base in self.bases: |
76 for base in self.bases: |
72 if base != nullrev: |
77 if base != nullrev: |
73 revs.difference_update(self.ancs[base]) |
78 revs.difference_update(self.ancs[base]) |
74 revs.discard(nullrev) |
79 revs.discard(nullrev) |
|
80 |
75 def missingancestors(self, revs): |
81 def missingancestors(self, revs): |
76 res = set() |
82 res = set() |
77 for rev in revs: |
83 for rev in revs: |
78 if rev != nullrev: |
84 if rev != nullrev: |
79 res.update(self.ancs[rev]) |
85 res.update(self.ancs[rev]) |
80 for base in self.bases: |
86 for base in self.bases: |
81 if base != nullrev: |
87 if base != nullrev: |
82 res.difference_update(self.ancs[base]) |
88 res.difference_update(self.ancs[base]) |
83 return sorted(res) |
89 return sorted(res) |
|
90 |
84 |
91 |
85 def test_missingancestors(seed, rng): |
92 def test_missingancestors(seed, rng): |
86 # empirically observed to take around 1 second |
93 # empirically observed to take around 1 second |
87 graphcount = 100 |
94 graphcount = 100 |
88 testcount = 10 |
95 testcount = 10 |
175 # |/ |
189 # |/ |
176 # o 1 |
190 # o 1 |
177 # | |
191 # | |
178 # o 0 |
192 # o 0 |
179 |
193 |
180 graph = {0: [-1, -1], 1: [0, -1], 2: [1, -1], 3: [1, -1], 4: [2, -1], |
194 graph = { |
181 5: [4, -1], 6: [4, -1], 7: [4, -1], 8: [-1, -1], 9: [6, 7], |
195 0: [-1, -1], |
182 10: [5, -1], 11: [3, 7], 12: [9, -1], 13: [8, -1]} |
196 1: [0, -1], |
|
197 2: [1, -1], |
|
198 3: [1, -1], |
|
199 4: [2, -1], |
|
200 5: [4, -1], |
|
201 6: [4, -1], |
|
202 7: [4, -1], |
|
203 8: [-1, -1], |
|
204 9: [6, 7], |
|
205 10: [5, -1], |
|
206 11: [3, 7], |
|
207 12: [9, -1], |
|
208 13: [8, -1], |
|
209 } |
|
210 |
183 |
211 |
184 def test_missingancestors_explicit(): |
212 def test_missingancestors_explicit(): |
185 """A few explicit cases, easier to check for catching errors in refactors. |
213 """A few explicit cases, easier to check for catching errors in refactors. |
186 |
214 |
187 The bigger graph at the end has been produced by the random generator |
215 The bigger graph at the end has been produced by the random generator |
188 above, and we have some evidence that the other tests don't cover it. |
216 above, and we have some evidence that the other tests don't cover it. |
189 """ |
217 """ |
190 for i, (bases, revs) in enumerate((({1, 2, 3, 4, 7}, set(xrange(10))), |
218 for i, (bases, revs) in enumerate( |
191 ({10}, set({11, 12, 13, 14})), |
219 ( |
192 ({7}, set({1, 2, 3, 4, 5})), |
220 ({1, 2, 3, 4, 7}, set(xrange(10))), |
193 )): |
221 ({10}, set({11, 12, 13, 14})), |
|
222 ({7}, set({1, 2, 3, 4, 5})), |
|
223 ) |
|
224 ): |
194 print("%% removeancestorsfrom(), example %d" % (i + 1)) |
225 print("%% removeancestorsfrom(), example %d" % (i + 1)) |
195 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
226 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
196 missanc.removeancestorsfrom(revs) |
227 missanc.removeancestorsfrom(revs) |
197 print("remaining (sorted): %s" % sorted(list(revs))) |
228 print("remaining (sorted): %s" % sorted(list(revs))) |
198 |
229 |
199 for i, (bases, revs) in enumerate((({10}, {11}), |
230 for i, (bases, revs) in enumerate( |
200 ({11}, {10}), |
231 (({10}, {11}), ({11}, {10}), ({7}, {9, 11}),) |
201 ({7}, {9, 11}), |
232 ): |
202 )): |
|
203 print("%% missingancestors(), example %d" % (i + 1)) |
233 print("%% missingancestors(), example %d" % (i + 1)) |
204 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
234 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
205 print("return %s" % missanc.missingancestors(revs)) |
235 print("return %s" % missanc.missingancestors(revs)) |
206 |
236 |
207 print("% removeancestorsfrom(), bigger graph") |
237 print("% removeancestorsfrom(), bigger graph") |
208 vecgraph = [ |
238 vecgraph = [ |
209 [-1, -1], [0, -1], [1, 0], [2, 1], [3, -1], [4, -1], [5, 1], |
239 [-1, -1], |
210 [2, -1], [7, -1], [8, -1], [9, -1], [10, 1], [3, -1], [12, -1], |
240 [0, -1], |
211 [13, -1], [14, -1], [4, -1], [16, -1], [17, -1], [18, -1], |
241 [1, 0], |
212 [19, 11], [20, -1], [21, -1], [22, -1], [23, -1], [2, -1], |
242 [2, 1], |
213 [3, -1], [26, 24], [27, -1], [28, -1], [12, -1], [1, -1], [1, 9], |
243 [3, -1], |
214 [32, -1], [33, -1], [34, 31], [35, -1], [36, 26], [37, -1], |
244 [4, -1], |
215 [38, -1], [39, -1], [40, -1], [41, -1], [42, 26], [0, -1], |
245 [5, 1], |
216 [44, -1], [45, 4], [40, -1], [47, -1], [36, 0], [49, -1], |
246 [2, -1], |
217 [-1, -1], [51, -1], [52, -1], [53, -1], [14, -1], |
247 [7, -1], |
218 [55, -1], [15, -1], [23, -1], [58, -1], [59, -1], [2, -1], |
248 [8, -1], |
219 [61, 59], [62, -1], [63, -1], [-1, -1], [65, -1], |
249 [9, -1], |
220 [66, -1], [67, -1], [68, -1], [37, 28], [69, 25], |
250 [10, 1], |
221 [71, -1], [72, -1], [50, 2], [74, -1], [12, -1], |
251 [3, -1], |
222 [18, -1], [77, -1], [78, -1], [79, -1], [43, 33], |
252 [12, -1], |
223 [81, -1], [82, -1], [83, -1], [84, 45], [85, -1], |
253 [13, -1], |
224 [86, -1], [-1, -1], [88, -1], [-1, -1], [76, 83], [44, -1], |
254 [14, -1], |
225 [92, -1], [93, -1], [9, -1], [95, 67], [96, -1], [97, -1], |
255 [4, -1], |
226 [-1, -1]] |
256 [16, -1], |
|
257 [17, -1], |
|
258 [18, -1], |
|
259 [19, 11], |
|
260 [20, -1], |
|
261 [21, -1], |
|
262 [22, -1], |
|
263 [23, -1], |
|
264 [2, -1], |
|
265 [3, -1], |
|
266 [26, 24], |
|
267 [27, -1], |
|
268 [28, -1], |
|
269 [12, -1], |
|
270 [1, -1], |
|
271 [1, 9], |
|
272 [32, -1], |
|
273 [33, -1], |
|
274 [34, 31], |
|
275 [35, -1], |
|
276 [36, 26], |
|
277 [37, -1], |
|
278 [38, -1], |
|
279 [39, -1], |
|
280 [40, -1], |
|
281 [41, -1], |
|
282 [42, 26], |
|
283 [0, -1], |
|
284 [44, -1], |
|
285 [45, 4], |
|
286 [40, -1], |
|
287 [47, -1], |
|
288 [36, 0], |
|
289 [49, -1], |
|
290 [-1, -1], |
|
291 [51, -1], |
|
292 [52, -1], |
|
293 [53, -1], |
|
294 [14, -1], |
|
295 [55, -1], |
|
296 [15, -1], |
|
297 [23, -1], |
|
298 [58, -1], |
|
299 [59, -1], |
|
300 [2, -1], |
|
301 [61, 59], |
|
302 [62, -1], |
|
303 [63, -1], |
|
304 [-1, -1], |
|
305 [65, -1], |
|
306 [66, -1], |
|
307 [67, -1], |
|
308 [68, -1], |
|
309 [37, 28], |
|
310 [69, 25], |
|
311 [71, -1], |
|
312 [72, -1], |
|
313 [50, 2], |
|
314 [74, -1], |
|
315 [12, -1], |
|
316 [18, -1], |
|
317 [77, -1], |
|
318 [78, -1], |
|
319 [79, -1], |
|
320 [43, 33], |
|
321 [81, -1], |
|
322 [82, -1], |
|
323 [83, -1], |
|
324 [84, 45], |
|
325 [85, -1], |
|
326 [86, -1], |
|
327 [-1, -1], |
|
328 [88, -1], |
|
329 [-1, -1], |
|
330 [76, 83], |
|
331 [44, -1], |
|
332 [92, -1], |
|
333 [93, -1], |
|
334 [9, -1], |
|
335 [95, 67], |
|
336 [96, -1], |
|
337 [97, -1], |
|
338 [-1, -1], |
|
339 ] |
227 problem_rev = 28 |
340 problem_rev = 28 |
228 problem_base = 70 |
341 problem_base = 70 |
229 # problem_rev is a parent of problem_base, but a faulty implementation |
342 # problem_rev is a parent of problem_base, but a faulty implementation |
230 # could forget to remove it. |
343 # could forget to remove it. |
231 bases = {60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6} |
344 bases = {60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6} |
279 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
400 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
280 |
401 |
281 # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0 |
402 # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0 |
282 s = genlazyancestors([10, 1], inclusive=True) |
403 s = genlazyancestors([10, 1], inclusive=True) |
283 printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1]) |
404 printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1]) |
|
405 |
284 |
406 |
285 # The C gca algorithm requires a real repo. These are textual descriptions of |
407 # The C gca algorithm requires a real repo. These are textual descriptions of |
286 # DAGs that have been known to be problematic, and, optionally, known pairs |
408 # DAGs that have been known to be problematic, and, optionally, known pairs |
287 # of revisions and their expected ancestor list. |
409 # of revisions and their expected ancestor list. |
288 dagtests = [ |
410 dagtests = [ |
289 (b'+2*2*2/*3/2', {}), |
411 (b'+2*2*2/*3/2', {}), |
290 (b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}), |
412 (b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}), |
291 (b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}), |
413 (b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}), |
292 ] |
414 ] |
|
415 |
|
416 |
293 def test_gca(): |
417 def test_gca(): |
294 u = uimod.ui.load() |
418 u = uimod.ui.load() |
295 for i, (dag, tests) in enumerate(dagtests): |
419 for i, (dag, tests) in enumerate(dagtests): |
296 repo = hg.repository(u, b'gca%d' % i, create=1) |
420 repo = hg.repository(u, b'gca%d' % i, create=1) |
297 cl = repo.changelog |
421 cl = repo.changelog |