144
127
self.assertGDFO(graph, 'a', 5)
145
128
self.assertGDFO(graph, 'c', 5)
147
def test_add_existing_node(self):
148
graph = self.make_known_graph(test_graph.ancestry_1)
149
# Add a node that already exists with identical content
151
self.assertGDFO(graph, 'rev4', 5)
152
graph.add_node('rev4', ['rev3', 'rev2b'])
153
self.assertGDFO(graph, 'rev4', 5)
154
# This also works if we use a tuple rather than a list
155
graph.add_node('rev4', ('rev3', 'rev2b'))
157
def test_add_existing_node_mismatched_parents(self):
158
graph = self.make_known_graph(test_graph.ancestry_1)
159
self.assertRaises(ValueError, graph.add_node, 'rev4',
162
def test_add_node_with_ghost_parent(self):
163
graph = self.make_known_graph(test_graph.ancestry_1)
164
graph.add_node('rev5', ['rev2b', 'revGhost'])
165
self.assertGDFO(graph, 'rev5', 4)
166
self.assertGDFO(graph, 'revGhost', 1)
168
def test_add_new_root(self):
169
graph = self.make_known_graph(test_graph.ancestry_1)
170
graph.add_node('rev5', [])
171
self.assertGDFO(graph, 'rev5', 1)
173
def test_add_with_all_ghost_parents(self):
174
graph = self.make_known_graph(test_graph.ancestry_1)
175
graph.add_node('rev5', ['ghost'])
176
self.assertGDFO(graph, 'rev5', 2)
177
self.assertGDFO(graph, 'ghost', 1)
179
def test_gdfo_after_add_node(self):
180
graph = self.make_known_graph(test_graph.ancestry_1)
181
self.assertEqual([], graph.get_child_keys('rev4'))
182
graph.add_node('rev5', ['rev4'])
183
self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
184
self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
185
self.assertEqual([], graph.get_child_keys('rev5'))
186
self.assertGDFO(graph, 'rev5', 6)
187
graph.add_node('rev6', ['rev2b'])
188
graph.add_node('rev7', ['rev6'])
189
graph.add_node('rev8', ['rev7', 'rev5'])
190
self.assertGDFO(graph, 'rev5', 6)
191
self.assertGDFO(graph, 'rev6', 4)
192
self.assertGDFO(graph, 'rev7', 5)
193
self.assertGDFO(graph, 'rev8', 7)
195
def test_fill_in_ghost(self):
196
graph = self.make_known_graph(test_graph.with_ghost)
197
# Add in a couple nodes and then fill in the 'ghost' so that it should
198
# cause renumbering of children nodes
199
graph.add_node('x', [])
200
graph.add_node('y', ['x'])
201
graph.add_node('z', ['y'])
202
graph.add_node('g', ['z'])
203
self.assertGDFO(graph, 'f', 2)
204
self.assertGDFO(graph, 'e', 3)
205
self.assertGDFO(graph, 'x', 1)
206
self.assertGDFO(graph, 'y', 2)
207
self.assertGDFO(graph, 'z', 3)
208
self.assertGDFO(graph, 'g', 4)
209
self.assertGDFO(graph, 'b', 4)
210
self.assertGDFO(graph, 'd', 5)
211
self.assertGDFO(graph, 'a', 5)
212
self.assertGDFO(graph, 'c', 6)
215
class TestKnownGraphHeads(TestCaseWithKnownGraph):
217
do_cache = None # Set by load_tests
219
130
def test_heads_null(self):
220
131
graph = self.make_known_graph(test_graph.ancestry_1)
221
132
self.assertEqual(set(['null:']), graph.heads(['null:']))
316
227
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
317
228
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
318
229
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
320
def test_filling_in_ghosts_resets_head_cache(self):
321
graph = self.make_known_graph(test_graph.with_ghost)
322
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
323
# 'g' is filled in, and decends from 'e', so the heads result is now
325
graph.add_node('g', ['e'])
326
self.assertEqual(set(['g']), graph.heads(['e', 'g']))
329
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
331
def assertTopoSortOrder(self, ancestry):
332
"""Check topo_sort and iter_topo_order is genuinely topological order.
334
For every child in the graph, check if it comes after all of it's
337
graph = self.make_known_graph(ancestry)
338
sort_result = graph.topo_sort()
339
# We should have an entry in sort_result for every entry present in the
341
self.assertEqual(len(ancestry), len(sort_result))
342
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
343
for node in sort_result:
344
parents = ancestry[node]
345
for parent in parents:
346
if parent not in ancestry:
349
if node_idx[node] <= node_idx[parent]:
350
self.fail("parent %s must come before child %s:\n%s"
351
% (parent, node, sort_result))
353
def test_topo_sort_empty(self):
354
"""TopoSort empty list"""
355
self.assertTopoSortOrder({})
357
def test_topo_sort_easy(self):
358
"""TopoSort list with one node"""
359
self.assertTopoSortOrder({0: []})
361
def test_topo_sort_cycle(self):
362
"""TopoSort traps graph with cycles"""
363
g = self.make_known_graph({0: [1],
365
self.assertRaises(errors.GraphCycleError, g.topo_sort)
367
def test_topo_sort_cycle_2(self):
368
"""TopoSort traps graph with longer cycle"""
369
g = self.make_known_graph({0: [1],
372
self.assertRaises(errors.GraphCycleError, g.topo_sort)
374
def test_topo_sort_cycle_with_tail(self):
375
"""TopoSort traps graph with longer cycle"""
376
g = self.make_known_graph({0: [1],
381
self.assertRaises(errors.GraphCycleError, g.topo_sort)
383
def test_topo_sort_1(self):
384
"""TopoSort simple nontrivial graph"""
385
self.assertTopoSortOrder({0: [3],
391
def test_topo_sort_partial(self):
392
"""Topological sort with partial ordering.
394
Multiple correct orderings are possible, so test for
395
correctness, not for exact match on the resulting list.
397
self.assertTopoSortOrder({0: [],
407
def test_topo_sort_ghost_parent(self):
408
"""Sort nodes, but don't include some parents in the output"""
409
self.assertTopoSortOrder({0: [1],
413
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
415
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
416
"""Check that merge based sorting and iter_topo_order on graph works."""
417
graph = self.make_known_graph(ancestry)
418
value = graph.merge_sort(branch_tip)
419
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
421
if result_list != value:
422
self.assertEqualDiff(pprint.pformat(result_list),
423
pprint.pformat(value))
425
def test_merge_sort_empty(self):
426
# sorting of an emptygraph does not error
427
self.assertSortAndIterate({}, None, [])
428
self.assertSortAndIterate({}, NULL_REVISION, [])
429
self.assertSortAndIterate({}, (NULL_REVISION,), [])
431
def test_merge_sort_not_empty_no_tip(self):
432
# merge sorting of a branch starting with None should result
433
# in an empty list: no revisions are dragged in.
434
self.assertSortAndIterate({0: []}, None, [])
435
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
436
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
438
def test_merge_sort_one_revision(self):
439
# sorting with one revision as the tip returns the correct fields:
440
# sequence - 0, revision id, merge depth - 0, end_of_merge
441
self.assertSortAndIterate({'id': []},
443
[('id', 0, (1,), True)])
445
def test_sequence_numbers_increase_no_merges(self):
446
# emit a few revisions with no merges to check the sequence
447
# numbering works in trivial cases
448
self.assertSortAndIterate(
453
[('C', 0, (3,), False),
454
('B', 0, (2,), False),
455
('A', 0, (1,), True),
459
def test_sequence_numbers_increase_with_merges(self):
460
# test that sequence numbers increase across merges
461
self.assertSortAndIterate(
466
[('C', 0, (2,), False),
467
('B', 1, (1,1,1), True),
468
('A', 0, (1,), True),
472
def test_merge_sort_race(self):
488
self.assertSortAndIterate(graph, 'F',
489
[('F', 0, (3,), False),
490
('D', 1, (2,2,1), False),
491
('C', 2, (2,1,1), True),
492
('B', 0, (2,), False),
493
('A', 0, (1,), True),
511
self.assertSortAndIterate(graph, 'F',
512
[('F', 0, (3,), False),
513
('D', 1, (2,1,2), False),
514
('C', 2, (2,2,1), True),
515
('X', 1, (2,1,1), True),
516
('B', 0, (2,), False),
517
('A', 0, (1,), True),
520
def test_merge_depth_with_nested_merges(self):
521
# the merge depth marker should reflect the depth of the revision
522
# in terms of merges out from the mainline
523
# revid, depth, parents:
532
self.assertSortAndIterate(
543
[('A', 0, (3,), False),
544
('B', 1, (1,3,2), False),
545
('C', 1, (1,3,1), True),
546
('D', 0, (2,), False),
547
('E', 1, (1,1,2), False),
548
('F', 2, (1,2,1), True),
549
('G', 1, (1,1,1), True),
550
('H', 0, (1,), True),
554
def test_dotted_revnos_with_simple_merges(self):
559
# D E F 3, 1.1.2, 1.2.1
561
# G H I 4, 1.2.2, 1.3.1
566
self.assertSortAndIterate(
581
[('L', 0, (6,), False),
582
('K', 1, (1,3,2), False),
583
('I', 1, (1,3,1), True),
584
('J', 0, (5,), False),
585
('H', 1, (1,2,2), False),
586
('F', 1, (1,2,1), True),
587
('G', 0, (4,), False),
588
('E', 1, (1,1,2), False),
589
('C', 1, (1,1,1), True),
590
('D', 0, (3,), False),
591
('B', 0, (2,), False),
592
('A', 0, (1,), True),
595
# Adding a shortcut from the first revision should not change any of
596
# the existing numbers
597
self.assertSortAndIterate(
614
[('N', 0, (7,), False),
615
('M', 1, (1,4,1), True),
616
('L', 0, (6,), False),
617
('K', 1, (1,3,2), False),
618
('I', 1, (1,3,1), True),
619
('J', 0, (5,), False),
620
('H', 1, (1,2,2), False),
621
('F', 1, (1,2,1), True),
622
('G', 0, (4,), False),
623
('E', 1, (1,1,2), False),
624
('C', 1, (1,1,1), True),
625
('D', 0, (3,), False),
626
('B', 0, (2,), False),
627
('A', 0, (1,), True),
631
def test_end_of_merge_not_last_revision_in_branch(self):
632
# within a branch only the last revision gets an
633
# end of merge marker.
634
self.assertSortAndIterate(
639
[('A', 0, (2,), False),
644
def test_end_of_merge_multiple_revisions_merged_at_once(self):
645
# when multiple branches are merged at once, both of their
646
# branch-endpoints should be listed as end-of-merge.
647
# Also, the order of the multiple merges should be
648
# left-right shown top to bottom.
649
# * means end of merge
658
self.assertSortAndIterate(
659
{'A': ['H', 'B', 'E'],
669
[('A', 0, (2,), False),
670
('B', 1, (1,3,2), False),
671
('C', 2, (1,4,1), True),
672
('D', 1, (1,3,1), True),
673
('E', 1, (1,1,2), False),
674
('F', 2, (1,2,1), True),
675
('G', 1, (1,1,1), True),
676
('H', 0, (1,), True),
680
def test_parallel_root_sequence_numbers_increase_with_merges(self):
681
"""When there are parallel roots, check their revnos."""
682
self.assertSortAndIterate(
687
[('C', 0, (2,), False),
688
('B', 1, (0,1,1), True),
689
('A', 0, (1,), True),
693
def test_revnos_are_globally_assigned(self):
694
"""revnos are assigned according to the revision they derive from."""
695
# in this test we setup a number of branches that all derive from
696
# the first revision, and then merge them one at a time, which
697
# should give the revisions as they merge numbers still deriving from
698
# the revision were based on.
699
# merge 3: J: ['G', 'I']
703
# merge 2: G: ['D', 'F']
707
# merge 1: D: ['A', 'C']
712
self.assertSortAndIterate(
725
[('J', 0, (4,), False),
726
('I', 1, (1,3,2), False),
727
('H', 1, (1,3,1), True),
728
('G', 0, (3,), False),
729
('F', 1, (1,2,2), False),
730
('E', 1, (1,2,1), True),
731
('D', 0, (2,), False),
732
('C', 1, (1,1,2), False),
733
('B', 1, (1,1,1), True),
734
('A', 0, (1,), True),
738
def test_roots_and_sub_branches_versus_ghosts(self):
739
"""Extra roots and their mini branches use the same numbering.
741
All of them use the 0-node numbering.
754
self.assertSortAndIterate(
775
[('R', 0, (6,), False),
776
('Q', 1, (0,4,5), False),
777
('P', 2, (0,6,1), True),
778
('O', 1, (0,4,4), False),
779
('N', 1, (0,4,3), False),
780
('M', 2, (0,5,1), True),
781
('L', 1, (0,4,2), False),
782
('K', 1, (0,4,1), True),
783
('J', 0, (5,), False),
784
('I', 1, (0,3,1), True),
785
('H', 0, (4,), False),
786
('G', 1, (0,1,3), False),
787
('F', 2, (0,2,1), True),
788
('E', 1, (0,1,2), False),
789
('D', 1, (0,1,1), True),
790
('C', 0, (3,), False),
791
('B', 0, (2,), False),
792
('A', 0, (1,), True),
796
def test_ghost(self):
797
# merge_sort should be able to ignore ghosts
803
self.assertSortAndIterate(
809
[('C', 0, (3,), False),
810
('B', 0, (2,), False),
811
('A', 0, (1,), True),
814
def test_lefthand_ghost(self):
820
self.assertSortAndIterate(
824
[('B', 0, (2,), False),
825
('A', 0, (1,), True),
828
def test_graph_cycle(self):
829
# merge_sort should fail with a simple error when a graph cycle is
841
self.assertRaises(errors.GraphCycleError,
842
self.assertSortAndIterate,
853
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
854
"""Test the sort order returned by gc_sort."""
856
def assertSorted(self, expected, parent_map):
857
graph = self.make_known_graph(parent_map)
858
value = graph.gc_sort()
859
if expected != value:
860
self.assertEqualDiff(pprint.pformat(expected),
861
pprint.pformat(value))
863
def test_empty(self):
864
self.assertSorted([], {})
866
def test_single(self):
867
self.assertSorted(['a'], {'a':()})
868
self.assertSorted([('a',)], {('a',):()})
869
self.assertSorted([('F', 'a')], {('F', 'a'):()})
871
def test_linear(self):
872
self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
873
self.assertSorted([('c',), ('b',), ('a',)],
874
{('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
875
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
876
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
877
('F', 'c'): (('F', 'b'),)})
879
def test_mixed_ancestries(self):
880
# Each prefix should be sorted separately
881
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
882
('G', 'c'), ('G', 'b'), ('G', 'a'),
883
('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
885
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
886
('F', 'c'): (('F', 'b'),),
887
('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
888
('G', 'c'): (('G', 'b'),),
889
('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
890
('Q', 'c'): (('Q', 'b'),),
893
def test_stable_sorting(self):
894
# the sort order should be stable even when extra nodes are added
895
self.assertSorted(['b', 'c', 'a'],
896
{'a':(), 'b':('a',), 'c':('a',)})
897
self.assertSorted(['b', 'c', 'd', 'a'],
898
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
899
self.assertSorted(['b', 'c', 'd', 'a'],
900
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
901
self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
902
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
904
self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
905
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
911
def test_skip_ghost(self):
912
self.assertSorted(['b', 'c', 'a'],
913
{'a':(), 'b':('a', 'ghost'), 'c':('a',)})
915
def test_skip_mainline_ghost(self):
916
self.assertSorted(['b', 'c', 'a'],
917
{'a':(), 'b':('ghost', 'a'), 'c':('a',)})
added
removed
bzrlib/tests/test__known_graph.py
