1
# Copyright (C) 2009 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Tests for the python and pyrex extensions of KnownGraph"""
27
from bzrlib.tests import test_graph
28
from bzrlib.revision import NULL_REVISION
31
def load_tests(standard_tests, module, loader):
32
"""Parameterize tests for all versions of groupcompress."""
34
('python', {'module': _known_graph_py, 'do_cache': True}),
37
('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
39
suite = loader.suiteClass()
40
if compiled_known_graph.available():
41
scenarios.append(('C', {'module': compiled_known_graph.module,
43
caching_scenarios.append(
44
('C-nocache', {'module': compiled_known_graph.module,
47
# the compiled module isn't available, so we add a failing test
48
class FailWithoutFeature(tests.TestCase):
50
self.requireFeature(compiled_known_graph)
51
suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
52
# TestKnownGraphHeads needs to be permutated with and without caching.
53
# All other TestKnownGraph tests only need to be tested across module
54
heads_suite, other_suite = tests.split_suite_by_condition(
55
standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
56
suite = tests.multiply_tests(other_suite, scenarios, suite)
57
suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
62
compiled_known_graph = tests.ModuleAvailableFeature('bzrlib._known_graph_pyx')
72
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
75
class TestCaseWithKnownGraph(tests.TestCase):
77
module = None # Set by load_tests
79
def make_known_graph(self, ancestry):
80
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
83
class TestKnownGraph(TestCaseWithKnownGraph):
85
def assertGDFO(self, graph, rev, gdfo):
86
node = graph._nodes[rev]
87
self.assertEqual(gdfo, node.gdfo)
89
def test_children_ancestry1(self):
90
graph = self.make_known_graph(test_graph.ancestry_1)
91
self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
92
self.assertEqual(['rev2a', 'rev2b'],
93
sorted(graph.get_child_keys('rev1')))
94
self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
95
self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
96
self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
97
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
99
def test_parent_ancestry1(self):
100
graph = self.make_known_graph(test_graph.ancestry_1)
101
self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
102
self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
103
self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
104
self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
105
self.assertEqual(['rev2b', 'rev3'],
106
sorted(graph.get_parent_keys('rev4')))
107
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
109
def test_parent_with_ghost(self):
110
graph = self.make_known_graph(test_graph.with_ghost)
111
self.assertEqual(None, graph.get_parent_keys('g'))
113
def test_gdfo_ancestry_1(self):
114
graph = self.make_known_graph(test_graph.ancestry_1)
115
self.assertGDFO(graph, 'rev1', 2)
116
self.assertGDFO(graph, 'rev2b', 3)
117
self.assertGDFO(graph, 'rev2a', 3)
118
self.assertGDFO(graph, 'rev3', 4)
119
self.assertGDFO(graph, 'rev4', 5)
121
def test_gdfo_feature_branch(self):
122
graph = self.make_known_graph(test_graph.feature_branch)
123
self.assertGDFO(graph, 'rev1', 2)
124
self.assertGDFO(graph, 'rev2b', 3)
125
self.assertGDFO(graph, 'rev3b', 4)
127
def test_gdfo_extended_history_shortcut(self):
128
graph = self.make_known_graph(test_graph.extended_history_shortcut)
129
self.assertGDFO(graph, 'a', 2)
130
self.assertGDFO(graph, 'b', 3)
131
self.assertGDFO(graph, 'c', 4)
132
self.assertGDFO(graph, 'd', 5)
133
self.assertGDFO(graph, 'e', 6)
134
self.assertGDFO(graph, 'f', 6)
136
def test_gdfo_with_ghost(self):
137
graph = self.make_known_graph(test_graph.with_ghost)
138
self.assertGDFO(graph, 'f', 2)
139
self.assertGDFO(graph, 'e', 3)
140
self.assertGDFO(graph, 'g', 1)
141
self.assertGDFO(graph, 'b', 4)
142
self.assertGDFO(graph, 'd', 4)
143
self.assertGDFO(graph, 'a', 5)
144
self.assertGDFO(graph, 'c', 5)
146
def test_add_existing_node(self):
147
graph = self.make_known_graph(test_graph.ancestry_1)
148
# Add a node that already exists with identical content
150
self.assertGDFO(graph, 'rev4', 5)
151
graph.add_node('rev4', ['rev3', 'rev2b'])
152
self.assertGDFO(graph, 'rev4', 5)
153
# This also works if we use a tuple rather than a list
154
graph.add_node('rev4', ('rev3', 'rev2b'))
156
def test_add_existing_node_mismatched_parents(self):
157
graph = self.make_known_graph(test_graph.ancestry_1)
158
self.assertRaises(ValueError, graph.add_node, 'rev4',
161
def test_add_node_with_ghost_parent(self):
162
graph = self.make_known_graph(test_graph.ancestry_1)
163
graph.add_node('rev5', ['rev2b', 'revGhost'])
164
self.assertGDFO(graph, 'rev5', 4)
165
self.assertGDFO(graph, 'revGhost', 1)
167
def test_add_new_root(self):
168
graph = self.make_known_graph(test_graph.ancestry_1)
169
graph.add_node('rev5', [])
170
self.assertGDFO(graph, 'rev5', 1)
172
def test_add_with_all_ghost_parents(self):
173
graph = self.make_known_graph(test_graph.ancestry_1)
174
graph.add_node('rev5', ['ghost'])
175
self.assertGDFO(graph, 'rev5', 2)
176
self.assertGDFO(graph, 'ghost', 1)
178
def test_gdfo_after_add_node(self):
179
graph = self.make_known_graph(test_graph.ancestry_1)
180
self.assertEqual([], graph.get_child_keys('rev4'))
181
graph.add_node('rev5', ['rev4'])
182
self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
183
self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
184
self.assertEqual([], graph.get_child_keys('rev5'))
185
self.assertGDFO(graph, 'rev5', 6)
186
graph.add_node('rev6', ['rev2b'])
187
graph.add_node('rev7', ['rev6'])
188
graph.add_node('rev8', ['rev7', 'rev5'])
189
self.assertGDFO(graph, 'rev5', 6)
190
self.assertGDFO(graph, 'rev6', 4)
191
self.assertGDFO(graph, 'rev7', 5)
192
self.assertGDFO(graph, 'rev8', 7)
194
def test_fill_in_ghost(self):
195
graph = self.make_known_graph(test_graph.with_ghost)
196
# Add in a couple nodes and then fill in the 'ghost' so that it should
197
# cause renumbering of children nodes
198
graph.add_node('x', [])
199
graph.add_node('y', ['x'])
200
graph.add_node('z', ['y'])
201
graph.add_node('g', ['z'])
202
self.assertGDFO(graph, 'f', 2)
203
self.assertGDFO(graph, 'e', 3)
204
self.assertGDFO(graph, 'x', 1)
205
self.assertGDFO(graph, 'y', 2)
206
self.assertGDFO(graph, 'z', 3)
207
self.assertGDFO(graph, 'g', 4)
208
self.assertGDFO(graph, 'b', 4)
209
self.assertGDFO(graph, 'd', 5)
210
self.assertGDFO(graph, 'a', 5)
211
self.assertGDFO(graph, 'c', 6)
214
class TestKnownGraphHeads(TestCaseWithKnownGraph):
216
do_cache = None # Set by load_tests
218
def test_heads_null(self):
219
graph = self.make_known_graph(test_graph.ancestry_1)
220
self.assertEqual(set(['null:']), graph.heads(['null:']))
221
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
222
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
223
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
224
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
226
def test_heads_one(self):
227
# A single node will always be a head
228
graph = self.make_known_graph(test_graph.ancestry_1)
229
self.assertEqual(set(['null:']), graph.heads(['null:']))
230
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
231
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
232
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
233
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
234
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
236
def test_heads_single(self):
237
graph = self.make_known_graph(test_graph.ancestry_1)
238
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
239
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
240
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
241
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
242
self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
243
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
244
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
245
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
246
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
248
def test_heads_two_heads(self):
249
graph = self.make_known_graph(test_graph.ancestry_1)
250
self.assertEqual(set(['rev2a', 'rev2b']),
251
graph.heads(['rev2a', 'rev2b']))
252
self.assertEqual(set(['rev3', 'rev2b']),
253
graph.heads(['rev3', 'rev2b']))
255
def test_heads_criss_cross(self):
256
graph = self.make_known_graph(test_graph.criss_cross)
257
self.assertEqual(set(['rev2a']),
258
graph.heads(['rev2a', 'rev1']))
259
self.assertEqual(set(['rev2b']),
260
graph.heads(['rev2b', 'rev1']))
261
self.assertEqual(set(['rev3a']),
262
graph.heads(['rev3a', 'rev1']))
263
self.assertEqual(set(['rev3b']),
264
graph.heads(['rev3b', 'rev1']))
265
self.assertEqual(set(['rev2a', 'rev2b']),
266
graph.heads(['rev2a', 'rev2b']))
267
self.assertEqual(set(['rev3a']),
268
graph.heads(['rev3a', 'rev2a']))
269
self.assertEqual(set(['rev3a']),
270
graph.heads(['rev3a', 'rev2b']))
271
self.assertEqual(set(['rev3a']),
272
graph.heads(['rev3a', 'rev2a', 'rev2b']))
273
self.assertEqual(set(['rev3b']),
274
graph.heads(['rev3b', 'rev2a']))
275
self.assertEqual(set(['rev3b']),
276
graph.heads(['rev3b', 'rev2b']))
277
self.assertEqual(set(['rev3b']),
278
graph.heads(['rev3b', 'rev2a', 'rev2b']))
279
self.assertEqual(set(['rev3a', 'rev3b']),
280
graph.heads(['rev3a', 'rev3b']))
281
self.assertEqual(set(['rev3a', 'rev3b']),
282
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
284
def test_heads_shortcut(self):
285
graph = self.make_known_graph(test_graph.history_shortcut)
286
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
287
graph.heads(['rev2a', 'rev2b', 'rev2c']))
288
self.assertEqual(set(['rev3a', 'rev3b']),
289
graph.heads(['rev3a', 'rev3b']))
290
self.assertEqual(set(['rev3a', 'rev3b']),
291
graph.heads(['rev2a', 'rev3a', 'rev3b']))
292
self.assertEqual(set(['rev2a', 'rev3b']),
293
graph.heads(['rev2a', 'rev3b']))
294
self.assertEqual(set(['rev2c', 'rev3a']),
295
graph.heads(['rev2c', 'rev3a']))
297
def test_heads_linear(self):
298
graph = self.make_known_graph(test_graph.racing_shortcuts)
299
self.assertEqual(set(['w']), graph.heads(['w', 's']))
300
self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
301
self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
302
self.assertEqual(set(['z']), graph.heads(['s', 'z']))
304
def test_heads_alt_merge(self):
305
graph = self.make_known_graph(alt_merge)
306
self.assertEqual(set(['c']), graph.heads(['a', 'c']))
308
def test_heads_with_ghost(self):
309
graph = self.make_known_graph(test_graph.with_ghost)
310
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
311
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
312
self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
313
self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
314
self.assertEqual(set(['c']), graph.heads(['c', 'g']))
315
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
316
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
317
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
319
def test_filling_in_ghosts_resets_head_cache(self):
320
graph = self.make_known_graph(test_graph.with_ghost)
321
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
322
# 'g' is filled in, and decends from 'e', so the heads result is now
324
graph.add_node('g', ['e'])
325
self.assertEqual(set(['g']), graph.heads(['e', 'g']))
328
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
330
def assertTopoSortOrder(self, ancestry):
331
"""Check topo_sort and iter_topo_order is genuinely topological order.
333
For every child in the graph, check if it comes after all of it's
336
graph = self.make_known_graph(ancestry)
337
sort_result = graph.topo_sort()
338
# We should have an entry in sort_result for every entry present in the
340
self.assertEqual(len(ancestry), len(sort_result))
341
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
342
for node in sort_result:
343
parents = ancestry[node]
344
for parent in parents:
345
if parent not in ancestry:
348
if node_idx[node] <= node_idx[parent]:
349
self.fail("parent %s must come before child %s:\n%s"
350
% (parent, node, sort_result))
352
def test_topo_sort_empty(self):
353
"""TopoSort empty list"""
354
self.assertTopoSortOrder({})
356
def test_topo_sort_easy(self):
357
"""TopoSort list with one node"""
358
self.assertTopoSortOrder({0: []})
360
def test_topo_sort_cycle(self):
361
"""TopoSort traps graph with cycles"""
362
g = self.make_known_graph({0: [1],
364
self.assertRaises(errors.GraphCycleError, g.topo_sort)
366
def test_topo_sort_cycle_2(self):
367
"""TopoSort traps graph with longer cycle"""
368
g = self.make_known_graph({0: [1],
371
self.assertRaises(errors.GraphCycleError, g.topo_sort)
373
def test_topo_sort_cycle_with_tail(self):
374
"""TopoSort traps graph with longer cycle"""
375
g = self.make_known_graph({0: [1],
380
self.assertRaises(errors.GraphCycleError, g.topo_sort)
382
def test_topo_sort_1(self):
383
"""TopoSort simple nontrivial graph"""
384
self.assertTopoSortOrder({0: [3],
390
def test_topo_sort_partial(self):
391
"""Topological sort with partial ordering.
393
Multiple correct orderings are possible, so test for
394
correctness, not for exact match on the resulting list.
396
self.assertTopoSortOrder({0: [],
406
def test_topo_sort_ghost_parent(self):
407
"""Sort nodes, but don't include some parents in the output"""
408
self.assertTopoSortOrder({0: [1],
412
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
414
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
415
"""Check that merge based sorting and iter_topo_order on graph works."""
416
graph = self.make_known_graph(ancestry)
417
value = graph.merge_sort(branch_tip)
418
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
420
if result_list != value:
421
self.assertEqualDiff(pprint.pformat(result_list),
422
pprint.pformat(value))
424
def test_merge_sort_empty(self):
425
# sorting of an emptygraph does not error
426
self.assertSortAndIterate({}, None, [])
427
self.assertSortAndIterate({}, NULL_REVISION, [])
428
self.assertSortAndIterate({}, (NULL_REVISION,), [])
430
def test_merge_sort_not_empty_no_tip(self):
431
# merge sorting of a branch starting with None should result
432
# in an empty list: no revisions are dragged in.
433
self.assertSortAndIterate({0: []}, None, [])
434
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
435
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
437
def test_merge_sort_one_revision(self):
438
# sorting with one revision as the tip returns the correct fields:
439
# sequence - 0, revision id, merge depth - 0, end_of_merge
440
self.assertSortAndIterate({'id': []},
442
[('id', 0, (1,), True)])
444
def test_sequence_numbers_increase_no_merges(self):
445
# emit a few revisions with no merges to check the sequence
446
# numbering works in trivial cases
447
self.assertSortAndIterate(
452
[('C', 0, (3,), False),
453
('B', 0, (2,), False),
454
('A', 0, (1,), True),
458
def test_sequence_numbers_increase_with_merges(self):
459
# test that sequence numbers increase across merges
460
self.assertSortAndIterate(
465
[('C', 0, (2,), False),
466
('B', 1, (1,1,1), True),
467
('A', 0, (1,), True),
471
def test_merge_sort_race(self):
487
self.assertSortAndIterate(graph, 'F',
488
[('F', 0, (3,), False),
489
('D', 1, (2,2,1), False),
490
('C', 2, (2,1,1), True),
491
('B', 0, (2,), False),
492
('A', 0, (1,), True),
510
self.assertSortAndIterate(graph, 'F',
511
[('F', 0, (3,), False),
512
('D', 1, (2,1,2), False),
513
('C', 2, (2,2,1), True),
514
('X', 1, (2,1,1), True),
515
('B', 0, (2,), False),
516
('A', 0, (1,), True),
519
def test_merge_depth_with_nested_merges(self):
520
# the merge depth marker should reflect the depth of the revision
521
# in terms of merges out from the mainline
522
# revid, depth, parents:
531
self.assertSortAndIterate(
542
[('A', 0, (3,), False),
543
('B', 1, (1,3,2), False),
544
('C', 1, (1,3,1), True),
545
('D', 0, (2,), False),
546
('E', 1, (1,1,2), False),
547
('F', 2, (1,2,1), True),
548
('G', 1, (1,1,1), True),
549
('H', 0, (1,), True),
553
def test_dotted_revnos_with_simple_merges(self):
558
# D E F 3, 1.1.2, 1.2.1
560
# G H I 4, 1.2.2, 1.3.1
565
self.assertSortAndIterate(
580
[('L', 0, (6,), False),
581
('K', 1, (1,3,2), False),
582
('I', 1, (1,3,1), True),
583
('J', 0, (5,), False),
584
('H', 1, (1,2,2), False),
585
('F', 1, (1,2,1), True),
586
('G', 0, (4,), False),
587
('E', 1, (1,1,2), False),
588
('C', 1, (1,1,1), True),
589
('D', 0, (3,), False),
590
('B', 0, (2,), False),
591
('A', 0, (1,), True),
594
# Adding a shortcut from the first revision should not change any of
595
# the existing numbers
596
self.assertSortAndIterate(
613
[('N', 0, (7,), False),
614
('M', 1, (1,4,1), True),
615
('L', 0, (6,), False),
616
('K', 1, (1,3,2), False),
617
('I', 1, (1,3,1), True),
618
('J', 0, (5,), False),
619
('H', 1, (1,2,2), False),
620
('F', 1, (1,2,1), True),
621
('G', 0, (4,), False),
622
('E', 1, (1,1,2), False),
623
('C', 1, (1,1,1), True),
624
('D', 0, (3,), False),
625
('B', 0, (2,), False),
626
('A', 0, (1,), True),
630
def test_end_of_merge_not_last_revision_in_branch(self):
631
# within a branch only the last revision gets an
632
# end of merge marker.
633
self.assertSortAndIterate(
638
[('A', 0, (2,), False),
643
def test_end_of_merge_multiple_revisions_merged_at_once(self):
644
# when multiple branches are merged at once, both of their
645
# branch-endpoints should be listed as end-of-merge.
646
# Also, the order of the multiple merges should be
647
# left-right shown top to bottom.
648
# * means end of merge
657
self.assertSortAndIterate(
658
{'A': ['H', 'B', 'E'],
668
[('A', 0, (2,), False),
669
('B', 1, (1,3,2), False),
670
('C', 2, (1,4,1), True),
671
('D', 1, (1,3,1), True),
672
('E', 1, (1,1,2), False),
673
('F', 2, (1,2,1), True),
674
('G', 1, (1,1,1), True),
675
('H', 0, (1,), True),
679
def test_parallel_root_sequence_numbers_increase_with_merges(self):
680
"""When there are parallel roots, check their revnos."""
681
self.assertSortAndIterate(
686
[('C', 0, (2,), False),
687
('B', 1, (0,1,1), True),
688
('A', 0, (1,), True),
692
def test_revnos_are_globally_assigned(self):
693
"""revnos are assigned according to the revision they derive from."""
694
# in this test we setup a number of branches that all derive from
695
# the first revision, and then merge them one at a time, which
696
# should give the revisions as they merge numbers still deriving from
697
# the revision were based on.
698
# merge 3: J: ['G', 'I']
702
# merge 2: G: ['D', 'F']
706
# merge 1: D: ['A', 'C']
711
self.assertSortAndIterate(
724
[('J', 0, (4,), False),
725
('I', 1, (1,3,2), False),
726
('H', 1, (1,3,1), True),
727
('G', 0, (3,), False),
728
('F', 1, (1,2,2), False),
729
('E', 1, (1,2,1), True),
730
('D', 0, (2,), False),
731
('C', 1, (1,1,2), False),
732
('B', 1, (1,1,1), True),
733
('A', 0, (1,), True),
737
def test_roots_and_sub_branches_versus_ghosts(self):
738
"""Extra roots and their mini branches use the same numbering.
740
All of them use the 0-node numbering.
753
self.assertSortAndIterate(
774
[('R', 0, (6,), False),
775
('Q', 1, (0,4,5), False),
776
('P', 2, (0,6,1), True),
777
('O', 1, (0,4,4), False),
778
('N', 1, (0,4,3), False),
779
('M', 2, (0,5,1), True),
780
('L', 1, (0,4,2), False),
781
('K', 1, (0,4,1), True),
782
('J', 0, (5,), False),
783
('I', 1, (0,3,1), True),
784
('H', 0, (4,), False),
785
('G', 1, (0,1,3), False),
786
('F', 2, (0,2,1), True),
787
('E', 1, (0,1,2), False),
788
('D', 1, (0,1,1), True),
789
('C', 0, (3,), False),
790
('B', 0, (2,), False),
791
('A', 0, (1,), True),
795
def test_ghost(self):
796
# merge_sort should be able to ignore ghosts
802
self.assertSortAndIterate(
808
[('C', 0, (3,), False),
809
('B', 0, (2,), False),
810
('A', 0, (1,), True),
813
def test_lefthand_ghost(self):
819
self.assertSortAndIterate(
823
[('B', 0, (2,), False),
824
('A', 0, (1,), True),
827
def test_graph_cycle(self):
828
# merge_sort should fail with a simple error when a graph cycle is
840
self.assertRaises(errors.GraphCycleError,
841
self.assertSortAndIterate,
852
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
853
"""Test the sort order returned by gc_sort."""
855
def assertSorted(self, expected, parent_map):
856
graph = self.make_known_graph(parent_map)
857
value = graph.gc_sort()
858
if expected != value:
859
self.assertEqualDiff(pprint.pformat(expected),
860
pprint.pformat(value))
862
def test_empty(self):
863
self.assertSorted([], {})
865
def test_single(self):
866
self.assertSorted(['a'], {'a':()})
867
self.assertSorted([('a',)], {('a',):()})
868
self.assertSorted([('F', 'a')], {('F', 'a'):()})
870
def test_linear(self):
871
self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
872
self.assertSorted([('c',), ('b',), ('a',)],
873
{('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
874
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
875
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
876
('F', 'c'): (('F', 'b'),)})
878
def test_mixed_ancestries(self):
879
# Each prefix should be sorted separately
880
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
881
('G', 'c'), ('G', 'b'), ('G', 'a'),
882
('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
884
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
885
('F', 'c'): (('F', 'b'),),
886
('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
887
('G', 'c'): (('G', 'b'),),
888
('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
889
('Q', 'c'): (('Q', 'b'),),
892
def test_stable_sorting(self):
893
# the sort order should be stable even when extra nodes are added
894
self.assertSorted(['b', 'c', 'a'],
895
{'a':(), 'b':('a',), 'c':('a',)})
896
self.assertSorted(['b', 'c', 'd', 'a'],
897
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
898
self.assertSorted(['b', 'c', 'd', 'a'],
899
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
900
self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
901
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
903
self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
904
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
910
def test_skip_ghost(self):
911
self.assertSorted(['b', 'c', 'a'],
912
{'a':(), 'b':('a', 'ghost'), 'c':('a',)})
914
def test_skip_mainline_ghost(self):
915
self.assertSorted(['b', 'c', 'a'],
916
{'a':(), 'b':('ghost', 'a'), 'c':('a',)})
added
removed
bzrlib/tests/test__known_graph.py
