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_feature.available():
41
scenarios.append(('C', {'module': compiled_known_graph_feature.module,
43
caching_scenarios.append(
44
('C-nocache', {'module': compiled_known_graph_feature.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_feature)
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_feature = tests.ModuleAvailableFeature(
63
'bzrlib._known_graph_pyx')
73
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
76
class TestCaseWithKnownGraph(tests.TestCase):
78
module = None # Set by load_tests
80
def make_known_graph(self, ancestry):
81
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
84
class TestKnownGraph(TestCaseWithKnownGraph):
86
def assertGDFO(self, graph, rev, gdfo):
87
node = graph._nodes[rev]
88
self.assertEqual(gdfo, node.gdfo)
90
def test_children_ancestry1(self):
91
graph = self.make_known_graph(test_graph.ancestry_1)
92
self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
93
self.assertEqual(['rev2a', 'rev2b'],
94
sorted(graph.get_child_keys('rev1')))
95
self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
96
self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
97
self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
98
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
100
def test_parent_ancestry1(self):
101
graph = self.make_known_graph(test_graph.ancestry_1)
102
self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
103
self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
104
self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
105
self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
106
self.assertEqual(['rev2b', 'rev3'],
107
sorted(graph.get_parent_keys('rev4')))
108
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
110
def test_parent_with_ghost(self):
111
graph = self.make_known_graph(test_graph.with_ghost)
112
self.assertEqual(None, graph.get_parent_keys('g'))
114
def test_gdfo_ancestry_1(self):
115
graph = self.make_known_graph(test_graph.ancestry_1)
116
self.assertGDFO(graph, 'rev1', 2)
117
self.assertGDFO(graph, 'rev2b', 3)
118
self.assertGDFO(graph, 'rev2a', 3)
119
self.assertGDFO(graph, 'rev3', 4)
120
self.assertGDFO(graph, 'rev4', 5)
122
def test_gdfo_feature_branch(self):
123
graph = self.make_known_graph(test_graph.feature_branch)
124
self.assertGDFO(graph, 'rev1', 2)
125
self.assertGDFO(graph, 'rev2b', 3)
126
self.assertGDFO(graph, 'rev3b', 4)
128
def test_gdfo_extended_history_shortcut(self):
129
graph = self.make_known_graph(test_graph.extended_history_shortcut)
130
self.assertGDFO(graph, 'a', 2)
131
self.assertGDFO(graph, 'b', 3)
132
self.assertGDFO(graph, 'c', 4)
133
self.assertGDFO(graph, 'd', 5)
134
self.assertGDFO(graph, 'e', 6)
135
self.assertGDFO(graph, 'f', 6)
137
def test_gdfo_with_ghost(self):
138
graph = self.make_known_graph(test_graph.with_ghost)
139
self.assertGDFO(graph, 'f', 2)
140
self.assertGDFO(graph, 'e', 3)
141
self.assertGDFO(graph, 'g', 1)
142
self.assertGDFO(graph, 'b', 4)
143
self.assertGDFO(graph, 'd', 4)
144
self.assertGDFO(graph, 'a', 5)
145
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
def test_heads_null(self):
220
graph = self.make_known_graph(test_graph.ancestry_1)
221
self.assertEqual(set(['null:']), graph.heads(['null:']))
222
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
223
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
224
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
225
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
227
def test_heads_one(self):
228
# A single node will always be a head
229
graph = self.make_known_graph(test_graph.ancestry_1)
230
self.assertEqual(set(['null:']), graph.heads(['null:']))
231
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
232
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
233
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
234
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
235
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
237
def test_heads_single(self):
238
graph = self.make_known_graph(test_graph.ancestry_1)
239
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
240
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
241
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
242
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
243
self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
244
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
245
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
246
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
247
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
249
def test_heads_two_heads(self):
250
graph = self.make_known_graph(test_graph.ancestry_1)
251
self.assertEqual(set(['rev2a', 'rev2b']),
252
graph.heads(['rev2a', 'rev2b']))
253
self.assertEqual(set(['rev3', 'rev2b']),
254
graph.heads(['rev3', 'rev2b']))
256
def test_heads_criss_cross(self):
257
graph = self.make_known_graph(test_graph.criss_cross)
258
self.assertEqual(set(['rev2a']),
259
graph.heads(['rev2a', 'rev1']))
260
self.assertEqual(set(['rev2b']),
261
graph.heads(['rev2b', 'rev1']))
262
self.assertEqual(set(['rev3a']),
263
graph.heads(['rev3a', 'rev1']))
264
self.assertEqual(set(['rev3b']),
265
graph.heads(['rev3b', 'rev1']))
266
self.assertEqual(set(['rev2a', 'rev2b']),
267
graph.heads(['rev2a', 'rev2b']))
268
self.assertEqual(set(['rev3a']),
269
graph.heads(['rev3a', 'rev2a']))
270
self.assertEqual(set(['rev3a']),
271
graph.heads(['rev3a', 'rev2b']))
272
self.assertEqual(set(['rev3a']),
273
graph.heads(['rev3a', 'rev2a', 'rev2b']))
274
self.assertEqual(set(['rev3b']),
275
graph.heads(['rev3b', 'rev2a']))
276
self.assertEqual(set(['rev3b']),
277
graph.heads(['rev3b', 'rev2b']))
278
self.assertEqual(set(['rev3b']),
279
graph.heads(['rev3b', 'rev2a', 'rev2b']))
280
self.assertEqual(set(['rev3a', 'rev3b']),
281
graph.heads(['rev3a', 'rev3b']))
282
self.assertEqual(set(['rev3a', 'rev3b']),
283
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
285
def test_heads_shortcut(self):
286
graph = self.make_known_graph(test_graph.history_shortcut)
287
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
288
graph.heads(['rev2a', 'rev2b', 'rev2c']))
289
self.assertEqual(set(['rev3a', 'rev3b']),
290
graph.heads(['rev3a', 'rev3b']))
291
self.assertEqual(set(['rev3a', 'rev3b']),
292
graph.heads(['rev2a', 'rev3a', 'rev3b']))
293
self.assertEqual(set(['rev2a', 'rev3b']),
294
graph.heads(['rev2a', 'rev3b']))
295
self.assertEqual(set(['rev2c', 'rev3a']),
296
graph.heads(['rev2c', 'rev3a']))
298
def test_heads_linear(self):
299
graph = self.make_known_graph(test_graph.racing_shortcuts)
300
self.assertEqual(set(['w']), graph.heads(['w', 's']))
301
self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
302
self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
303
self.assertEqual(set(['z']), graph.heads(['s', 'z']))
305
def test_heads_alt_merge(self):
306
graph = self.make_known_graph(alt_merge)
307
self.assertEqual(set(['c']), graph.heads(['a', 'c']))
309
def test_heads_with_ghost(self):
310
graph = self.make_known_graph(test_graph.with_ghost)
311
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
312
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
313
self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
314
self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
315
self.assertEqual(set(['c']), graph.heads(['c', 'g']))
316
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
317
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
318
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
