« back to all changes in this revision
Viewing changes to bzrlib/tests/test__known_graph.py
- browse files at revision 4629
- compare with another revision
- compare with revision 0.17.26
- download diff
- download tarball
- view history from revision 4629
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-08-19 18:04:49 UTC
- mfrom: (4593.5.43 1.19-known-graph-sorted)
- Revision ID: pqm@pqm.ubuntu.com-20090819180449-p5dibldf9pcp24n4
(jam) Add VersionedFiles.get_known_graph_ancestry and
KnownGraph.merge_sort()
KnownGraph.merge_sort()
- files renamed:
- bzrlib/tests/test_versionedfile.py => bzrlib/tests/per_versionedfile.py
- files modified:
- NEWS
added
removed
bzrlib/tests/test__known_graph.py
16
16
17
17
"""Tests for the python and pyrex extensions of KnownGraph"""
18
18
19
import pprint
20
19
21
from bzrlib import (
20
22
errors,
21
23
graph as _mod_graph,
30
32
"""Parameterize tests for all versions of groupcompress."""
31
33
scenarios = [
32
34
('python', {'module': _known_graph_py, 'do_cache': True}),
35
]
36
caching_scenarios = [
33
37
('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
34
38
]
35
39
suite = loader.suiteClass()
36
40
if CompiledKnownGraphFeature.available():
37
41
from bzrlib import _known_graph_pyx
38
42
scenarios.append(('C', {'module': _known_graph_pyx, 'do_cache': True}))
39
scenarios.append(('C-nocache',
43
caching_scenarios.append(('C-nocache',
40
44
{'module': _known_graph_pyx, 'do_cache': False}))
41
45
else:
42
46
# the compiled module isn't available, so we add a failing test
44
48
def test_fail(self):
45
49
self.requireFeature(CompiledKnownGraphFeature)
46
50
suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
47
result = tests.multiply_tests(standard_tests, scenarios, suite)
48
return result
51
# TestKnownGraphHeads needs to be permutated with and without caching.
52
# All other TestKnownGraph tests only need to be tested across module
53
heads_suite, other_suite = tests.split_suite_by_condition(
54
standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
55
suite = tests.multiply_tests(other_suite, scenarios, suite)
56
suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
57
suite)
58
return suite
49
59
50
60
51
61
class _CompiledKnownGraphFeature(tests.Feature):
73
83
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
74
84
75
85
76
class TestKnownGraph(tests.TestCase):
86
class TestCaseWithKnownGraph(tests.TestCase):
77
87
78
88
module = None # Set by load_tests
79
do_cache = None # Set by load_tests
80
89
81
90
def make_known_graph(self, ancestry):
82
91
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
83
92
93
94
class TestKnownGraph(TestCaseWithKnownGraph):
95
84
96
def assertGDFO(self, graph, rev, gdfo):
85
97
node = graph._nodes[rev]
86
98
self.assertEqual(gdfo, node.gdfo)
127
139
self.assertGDFO(graph, 'a', 5)
128
140
self.assertGDFO(graph, 'c', 5)
129
141
142
143
class TestKnownGraphHeads(TestCaseWithKnownGraph):
144
145
do_cache = None # Set by load_tests
146
130
147
def test_heads_null(self):
131
148
graph = self.make_known_graph(test_graph.ancestry_1)
132
149
self.assertEqual(set(['null:']), graph.heads(['null:']))
227
244
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
228
245
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
229
246
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
247
248
249
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
250
251
def assertTopoSortOrder(self, ancestry):
252
"""Check topo_sort and iter_topo_order is genuinely topological order.
253
254
For every child in the graph, check if it comes after all of it's
255
parents.
256
"""
257
graph = self.make_known_graph(ancestry)
258
sort_result = graph.topo_sort()
259
# We should have an entry in sort_result for every entry present in the
260
# graph.
261
self.assertEqual(len(ancestry), len(sort_result))
262
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
263
for node in sort_result:
264
parents = ancestry[node]
265
for parent in parents:
266
if parent not in ancestry:
267
# ghost
268
continue
269
if node_idx[node] <= node_idx[parent]:
270
self.fail("parent %s must come before child %s:\n%s"
271
% (parent, node, sort_result))
272
273
def test_topo_sort_empty(self):
274
"""TopoSort empty list"""
275
self.assertTopoSortOrder({})
276
277
def test_topo_sort_easy(self):
278
"""TopoSort list with one node"""
279
self.assertTopoSortOrder({0: []})
280
281
def test_topo_sort_cycle(self):
282
"""TopoSort traps graph with cycles"""
283
g = self.make_known_graph({0: [1],
284
1: [0]})
285
self.assertRaises(errors.GraphCycleError, g.topo_sort)
286
287
def test_topo_sort_cycle_2(self):
288
"""TopoSort traps graph with longer cycle"""
289
g = self.make_known_graph({0: [1],
290
1: [2],
291
2: [0]})
292
self.assertRaises(errors.GraphCycleError, g.topo_sort)
293
294
def test_topo_sort_cycle_with_tail(self):
295
"""TopoSort traps graph with longer cycle"""
296
g = self.make_known_graph({0: [1],
297
1: [2],
298
2: [3, 4],
299
3: [0],
300
4: []})
301
self.assertRaises(errors.GraphCycleError, g.topo_sort)
302
303
def test_topo_sort_1(self):
304
"""TopoSort simple nontrivial graph"""
305
self.assertTopoSortOrder({0: [3],
306
1: [4],
307
2: [1, 4],
308
3: [],
309
4: [0, 3]})
310
311
def test_topo_sort_partial(self):
312
"""Topological sort with partial ordering.
313
314
Multiple correct orderings are possible, so test for
315
correctness, not for exact match on the resulting list.
316
"""
317
self.assertTopoSortOrder({0: [],
318
1: [0],
319
2: [0],
320
3: [0],
321
4: [1, 2, 3],
322
5: [1, 2],
323
6: [1, 2],
324
7: [2, 3],
325
8: [0, 1, 4, 5, 6]})
326
327
def test_topo_sort_ghost_parent(self):
328
"""Sort nodes, but don't include some parents in the output"""
329
self.assertTopoSortOrder({0: [1],
330
1: [2]})
331
332
333
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
334
335
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
336
"""Check that merge based sorting and iter_topo_order on graph works."""
337
graph = self.make_known_graph(ancestry)
338
value = graph.merge_sort(branch_tip)
339
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
340
for n in value]
341
if result_list != value:
342
self.assertEqualDiff(pprint.pformat(result_list),
343
pprint.pformat(value))
344
345
def test_merge_sort_empty(self):
346
# sorting of an emptygraph does not error
347
self.assertSortAndIterate({}, None, [])
348
self.assertSortAndIterate({}, NULL_REVISION, [])
349
self.assertSortAndIterate({}, (NULL_REVISION,), [])
350
351
def test_merge_sort_not_empty_no_tip(self):
352
# merge sorting of a branch starting with None should result
353
# in an empty list: no revisions are dragged in.
354
self.assertSortAndIterate({0: []}, None, [])
355
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
356
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
357
358
def test_merge_sort_one_revision(self):
359
# sorting with one revision as the tip returns the correct fields:
360
# sequence - 0, revision id, merge depth - 0, end_of_merge
361
self.assertSortAndIterate({'id': []},
362
'id',
363
[('id', 0, (1,), True)])
364
365
def test_sequence_numbers_increase_no_merges(self):
366
# emit a few revisions with no merges to check the sequence
367
# numbering works in trivial cases
368
self.assertSortAndIterate(
369
{'A': [],
370
'B': ['A'],
371
'C': ['B']},
372
'C',
373
[('C', 0, (3,), False),
374
('B', 0, (2,), False),
375
('A', 0, (1,), True),
376
],
377
)
378
379
def test_sequence_numbers_increase_with_merges(self):
380
# test that sequence numbers increase across merges
381
self.assertSortAndIterate(
382
{'A': [],
383
'B': ['A'],
384
'C': ['A', 'B']},
385
'C',
386
[('C', 0, (2,), False),
387
('B', 1, (1,1,1), True),
388
('A', 0, (1,), True),
389
],
390
)
391
392
def test_merge_sort_race(self):
393
# A
394
# |
395
# B-.
396
# |\ \
397
# | | C
398
# | |/
399
# | D
400
# |/
401
# F
402
graph = {'A': [],
403
'B': ['A'],
404
'C': ['B'],
405
'D': ['B', 'C'],
406
'F': ['B', 'D'],
407
}
408
self.assertSortAndIterate(graph, 'F',
409
[('F', 0, (3,), False),
410
('D', 1, (2,2,1), False),
411
('C', 2, (2,1,1), True),
412
('B', 0, (2,), False),
413
('A', 0, (1,), True),
414
])
415
# A
416
# |
417
# B-.
418
# |\ \
419
# | X C
420
# | |/
421
# | D
422
# |/
423
# F
424
graph = {'A': [],
425
'B': ['A'],
426
'C': ['B'],
427
'X': ['B'],
428
'D': ['X', 'C'],
429
'F': ['B', 'D'],
430
}
431
self.assertSortAndIterate(graph, 'F',
432
[('F', 0, (3,), False),
433
('D', 1, (2,1,2), False),
434
('C', 2, (2,2,1), True),
435
('X', 1, (2,1,1), True),
436
('B', 0, (2,), False),
437
('A', 0, (1,), True),
438
])
439
440
def test_merge_depth_with_nested_merges(self):
441
# the merge depth marker should reflect the depth of the revision
442
# in terms of merges out from the mainline
443
# revid, depth, parents:
444
# A 0 [D, B]
445
# B 1 [C, F]
446
# C 1 [H]
447
# D 0 [H, E]
448
# E 1 [G, F]
449
# F 2 [G]
450
# G 1 [H]
451
# H 0
452
self.assertSortAndIterate(
453
{'A': ['D', 'B'],
454
'B': ['C', 'F'],
455
'C': ['H'],
456
'D': ['H', 'E'],
457
'E': ['G', 'F'],
458
'F': ['G'],
459
'G': ['H'],
460
'H': []
461
},
462
'A',
463
[('A', 0, (3,), False),
464
('B', 1, (1,3,2), False),
465
('C', 1, (1,3,1), True),
466
('D', 0, (2,), False),
467
('E', 1, (1,1,2), False),
468
('F', 2, (1,2,1), True),
469
('G', 1, (1,1,1), True),
470
('H', 0, (1,), True),
471
],
472
)
473
474
def test_dotted_revnos_with_simple_merges(self):
475
# A 1
476
# |\
477
# B C 2, 1.1.1
478
# | |\
479
# D E F 3, 1.1.2, 1.2.1
480
# |/ /|
481
# G H I 4, 1.2.2, 1.3.1
482
# |/ /
483
# J K 5, 1.3.2
484
# |/
485
# L 6
486
self.assertSortAndIterate(
487
{'A': [],
488
'B': ['A'],
489
'C': ['A'],
490
'D': ['B'],
491
'E': ['C'],
492
'F': ['C'],
493
'G': ['D', 'E'],
494
'H': ['F'],
495
'I': ['F'],
496
'J': ['G', 'H'],
497
'K': ['I'],
498
'L': ['J', 'K'],
499
},
500
'L',
501
[('L', 0, (6,), False),
502
('K', 1, (1,3,2), False),
503
('I', 1, (1,3,1), True),
504
('J', 0, (5,), False),
505
('H', 1, (1,2,2), False),
506
('F', 1, (1,2,1), True),
507
('G', 0, (4,), False),
508
('E', 1, (1,1,2), False),
509
('C', 1, (1,1,1), True),
510
('D', 0, (3,), False),
511
('B', 0, (2,), False),
512
('A', 0, (1,), True),
513
],
514
)
515
# Adding a shortcut from the first revision should not change any of
516
# the existing numbers
517
self.assertSortAndIterate(
518
{'A': [],
519
'B': ['A'],
520
'C': ['A'],
521
'D': ['B'],
522
'E': ['C'],
523
'F': ['C'],
524
'G': ['D', 'E'],
525
'H': ['F'],
526
'I': ['F'],
527
'J': ['G', 'H'],
528
'K': ['I'],
529
'L': ['J', 'K'],
530
'M': ['A'],
531
'N': ['L', 'M'],
532
},
533
'N',
534
[('N', 0, (7,), False),
535
('M', 1, (1,4,1), True),
536
('L', 0, (6,), False),
537
('K', 1, (1,3,2), False),
538
('I', 1, (1,3,1), True),
539
('J', 0, (5,), False),
540
('H', 1, (1,2,2), False),
541
('F', 1, (1,2,1), True),
542
('G', 0, (4,), False),
543
('E', 1, (1,1,2), False),
544
('C', 1, (1,1,1), True),
545
('D', 0, (3,), False),
546
('B', 0, (2,), False),
547
('A', 0, (1,), True),
548
],
549
)
550
551
def test_end_of_merge_not_last_revision_in_branch(self):
552
# within a branch only the last revision gets an
553
# end of merge marker.
554
self.assertSortAndIterate(
555
{'A': ['B'],
556
'B': [],
557
},
558
'A',
559
[('A', 0, (2,), False),
560
('B', 0, (1,), True)
561
],
562
)
563
564
def test_end_of_merge_multiple_revisions_merged_at_once(self):
565
# when multiple branches are merged at once, both of their
566
# branch-endpoints should be listed as end-of-merge.
567
# Also, the order of the multiple merges should be
568
# left-right shown top to bottom.
569
# * means end of merge
570
# A 0 [H, B, E]
571
# B 1 [D, C]
572
# C 2 [D] *
573
# D 1 [H] *
574
# E 1 [G, F]
575
# F 2 [G] *
576
# G 1 [H] *
577
# H 0 [] *
578
self.assertSortAndIterate(
579
{'A': ['H', 'B', 'E'],
580
'B': ['D', 'C'],
581
'C': ['D'],
582
'D': ['H'],
583
'E': ['G', 'F'],
584
'F': ['G'],
585
'G': ['H'],
586
'H': [],
587
},
588
'A',
589
[('A', 0, (2,), False),
590
('B', 1, (1,3,2), False),
591
('C', 2, (1,4,1), True),
592
('D', 1, (1,3,1), True),
593
('E', 1, (1,1,2), False),
594
('F', 2, (1,2,1), True),
595
('G', 1, (1,1,1), True),
596
('H', 0, (1,), True),
597
],
598
)
599
600
def test_parallel_root_sequence_numbers_increase_with_merges(self):
601
"""When there are parallel roots, check their revnos."""
602
self.assertSortAndIterate(
603
{'A': [],
604
'B': [],
605
'C': ['A', 'B']},
606
'C',
607
[('C', 0, (2,), False),
608
('B', 1, (0,1,1), True),
609
('A', 0, (1,), True),
610
],
611
)
612
613
def test_revnos_are_globally_assigned(self):
614
"""revnos are assigned according to the revision they derive from."""
615
# in this test we setup a number of branches that all derive from
616
# the first revision, and then merge them one at a time, which
617
# should give the revisions as they merge numbers still deriving from
618
# the revision were based on.
619
# merge 3: J: ['G', 'I']
620
# branch 3:
621
# I: ['H']
622
# H: ['A']
623
# merge 2: G: ['D', 'F']
624
# branch 2:
625
# F: ['E']
626
# E: ['A']
627
# merge 1: D: ['A', 'C']
628
# branch 1:
629
# C: ['B']
630
# B: ['A']
631
# root: A: []
632
self.assertSortAndIterate(
633
{'J': ['G', 'I'],
634
'I': ['H',],
635
'H': ['A'],
636
'G': ['D', 'F'],
637
'F': ['E'],
638
'E': ['A'],
639
'D': ['A', 'C'],
640
'C': ['B'],
641
'B': ['A'],
642
'A': [],
643
},
644
'J',
645
[('J', 0, (4,), False),
646
('I', 1, (1,3,2), False),
647
('H', 1, (1,3,1), True),
648
('G', 0, (3,), False),
649
('F', 1, (1,2,2), False),
650
('E', 1, (1,2,1), True),
651
('D', 0, (2,), False),
652
('C', 1, (1,1,2), False),
653
('B', 1, (1,1,1), True),
654
('A', 0, (1,), True),
655
],
656
)
657
658
def test_roots_and_sub_branches_versus_ghosts(self):
659
"""Extra roots and their mini branches use the same numbering.
660
661
All of them use the 0-node numbering.
662
"""
663
# A D K
664
# | |\ |\
665
# B E F L M
666
# | |/ |/
667
# C G N
668
# |/ |\
669
# H I O P
670
# |/ |/
671
# J Q
672
# |.---'
673
# R
674
self.assertSortAndIterate(
675
{'A': [],
676
'B': ['A'],
677
'C': ['B'],
678
'D': [],
679
'E': ['D'],
680
'F': ['D'],
681
'G': ['E', 'F'],
682
'H': ['C', 'G'],
683
'I': [],
684
'J': ['H', 'I'],
685
'K': [],
686
'L': ['K'],
687
'M': ['K'],
688
'N': ['L', 'M'],
689
'O': ['N'],
690
'P': ['N'],
691
'Q': ['O', 'P'],
692
'R': ['J', 'Q'],
693
},
694
'R',
695
[('R', 0, (6,), False),
696
('Q', 1, (0,4,5), False),
697
('P', 2, (0,6,1), True),
698
('O', 1, (0,4,4), False),
699
('N', 1, (0,4,3), False),
700
('M', 2, (0,5,1), True),
701
('L', 1, (0,4,2), False),
702
('K', 1, (0,4,1), True),
703
('J', 0, (5,), False),
704
('I', 1, (0,3,1), True),
705
('H', 0, (4,), False),
706
('G', 1, (0,1,3), False),
707
('F', 2, (0,2,1), True),
708
('E', 1, (0,1,2), False),
709
('D', 1, (0,1,1), True),
710
('C', 0, (3,), False),
711
('B', 0, (2,), False),
712
('A', 0, (1,), True),
713
],
714
)
715
716
def test_ghost(self):
717
# merge_sort should be able to ignore ghosts
718
# A
719
# |
720
# B ghost
721
# |/
722
# C
723
self.assertSortAndIterate(
724
{'A': [],
725
'B': ['A'],
726
'C': ['B', 'ghost'],
727
},
728
'C',
729
[('C', 0, (3,), False),
730
('B', 0, (2,), False),
731
('A', 0, (1,), True),
732
])
733
734
def test_graph_cycle(self):
735
# merge_sort should fail with a simple error when a graph cycle is
736
# encountered.
737
#
738
# A
739
# |,-.
740
# B |
741
# | |
742
# C ^
743
# | |
744
# D |
745
# |'-'
746
# E
747
self.assertRaises(errors.GraphCycleError,
748
self.assertSortAndIterate,
749
{'A': [],
750
'B': ['D'],
751
'C': ['B'],
752
'D': ['C'],
753
'E': ['D'],
754
},
755
'E',
756
[])
Loggerhead is a web-based interface for Breezy
Version: 2.0.1