1
# Copyright (C) 2009, 2010, 2011 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"""
26
from bzrlib.tests import test_graph
27
from bzrlib.revision import NULL_REVISION
28
from bzrlib.tests.scenarios import load_tests_apply_scenarios
31
def caching_scenarios():
33
('python', {'module': _known_graph_py, 'do_cache': True}),
35
if compiled_known_graph_feature.available():
36
scenarios.append(('C', {'module': compiled_known_graph_feature.module,
41
def non_caching_scenarios():
43
('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
45
if compiled_known_graph_feature.available():
47
('C-nocache', {'module': compiled_known_graph_feature.module,
52
load_tests = load_tests_apply_scenarios
55
compiled_known_graph_feature = tests.ModuleAvailableFeature(
56
'bzrlib._known_graph_pyx')
66
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
69
class TestCaseWithKnownGraph(tests.TestCase):
71
scenarios = caching_scenarios()
72
module = None # Set by load_tests
74
def make_known_graph(self, ancestry):
75
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
78
class TestKnownGraph(TestCaseWithKnownGraph):
80
def assertGDFO(self, graph, rev, gdfo):
81
node = graph._nodes[rev]
82
self.assertEqual(gdfo, node.gdfo)
84
def test_children_ancestry1(self):
85
graph = self.make_known_graph(test_graph.ancestry_1)
86
self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
87
self.assertEqual(['rev2a', 'rev2b'],
88
sorted(graph.get_child_keys('rev1')))
89
self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
90
self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
91
self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
92
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
94
def test_parent_ancestry1(self):
95
graph = self.make_known_graph(test_graph.ancestry_1)
96
self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
97
self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
98
self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
99
self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
100
self.assertEqual(['rev2b', 'rev3'],
101
sorted(graph.get_parent_keys('rev4')))
102
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
104
def test_parent_with_ghost(self):
105
graph = self.make_known_graph(test_graph.with_ghost)
106
self.assertEqual(None, graph.get_parent_keys('g'))
108
def test_gdfo_ancestry_1(self):
109
graph = self.make_known_graph(test_graph.ancestry_1)
110
self.assertGDFO(graph, 'rev1', 2)
111
self.assertGDFO(graph, 'rev2b', 3)
112
self.assertGDFO(graph, 'rev2a', 3)
113
self.assertGDFO(graph, 'rev3', 4)
114
self.assertGDFO(graph, 'rev4', 5)
116
def test_gdfo_feature_branch(self):
117
graph = self.make_known_graph(test_graph.feature_branch)
118
self.assertGDFO(graph, 'rev1', 2)
119
self.assertGDFO(graph, 'rev2b', 3)
120
self.assertGDFO(graph, 'rev3b', 4)
122
def test_gdfo_extended_history_shortcut(self):
123
graph = self.make_known_graph(test_graph.extended_history_shortcut)
124
self.assertGDFO(graph, 'a', 2)
125
self.assertGDFO(graph, 'b', 3)
126
self.assertGDFO(graph, 'c', 4)
127
self.assertGDFO(graph, 'd', 5)
128
self.assertGDFO(graph, 'e', 6)
129
self.assertGDFO(graph, 'f', 6)
131
def test_gdfo_with_ghost(self):
132
graph = self.make_known_graph(test_graph.with_ghost)
133
self.assertGDFO(graph, 'f', 2)
134
self.assertGDFO(graph, 'e', 3)
135
self.assertGDFO(graph, 'g', 1)
136
self.assertGDFO(graph, 'b', 4)
137
self.assertGDFO(graph, 'd', 4)
138
self.assertGDFO(graph, 'a', 5)
139
self.assertGDFO(graph, 'c', 5)
141
def test_add_existing_node(self):
142
graph = self.make_known_graph(test_graph.ancestry_1)
143
# Add a node that already exists with identical content
145
self.assertGDFO(graph, 'rev4', 5)
146
graph.add_node('rev4', ['rev3', 'rev2b'])
147
self.assertGDFO(graph, 'rev4', 5)
148
# This also works if we use a tuple rather than a list
149
graph.add_node('rev4', ('rev3', 'rev2b'))
151
def test_add_existing_node_mismatched_parents(self):
152
graph = self.make_known_graph(test_graph.ancestry_1)
153
self.assertRaises(ValueError, graph.add_node, 'rev4',
156
def test_add_node_with_ghost_parent(self):
157
graph = self.make_known_graph(test_graph.ancestry_1)
158
graph.add_node('rev5', ['rev2b', 'revGhost'])
159
self.assertGDFO(graph, 'rev5', 4)
160
self.assertGDFO(graph, 'revGhost', 1)
162
def test_add_new_root(self):
163
graph = self.make_known_graph(test_graph.ancestry_1)
164
graph.add_node('rev5', [])
165
self.assertGDFO(graph, 'rev5', 1)
167
def test_add_with_all_ghost_parents(self):
168
graph = self.make_known_graph(test_graph.ancestry_1)
169
graph.add_node('rev5', ['ghost'])
170
self.assertGDFO(graph, 'rev5', 2)
171
self.assertGDFO(graph, 'ghost', 1)
173
def test_gdfo_after_add_node(self):
174
graph = self.make_known_graph(test_graph.ancestry_1)
175
self.assertEqual([], graph.get_child_keys('rev4'))
176
graph.add_node('rev5', ['rev4'])
177
self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
178
self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
179
self.assertEqual([], graph.get_child_keys('rev5'))
180
self.assertGDFO(graph, 'rev5', 6)
181
graph.add_node('rev6', ['rev2b'])
182
graph.add_node('rev7', ['rev6'])
183
graph.add_node('rev8', ['rev7', 'rev5'])
184
self.assertGDFO(graph, 'rev5', 6)
185
self.assertGDFO(graph, 'rev6', 4)
186
self.assertGDFO(graph, 'rev7', 5)
187
self.assertGDFO(graph, 'rev8', 7)
189
def test_fill_in_ghost(self):
190
graph = self.make_known_graph(test_graph.with_ghost)
191
# Add in a couple nodes and then fill in the 'ghost' so that it should
192
# cause renumbering of children nodes
193
graph.add_node('x', [])
194
graph.add_node('y', ['x'])
195
graph.add_node('z', ['y'])
196
graph.add_node('g', ['z'])
197
self.assertGDFO(graph, 'f', 2)
198
self.assertGDFO(graph, 'e', 3)
199
self.assertGDFO(graph, 'x', 1)
200
self.assertGDFO(graph, 'y', 2)
201
self.assertGDFO(graph, 'z', 3)
202
self.assertGDFO(graph, 'g', 4)
203
self.assertGDFO(graph, 'b', 4)
204
self.assertGDFO(graph, 'd', 5)
205
self.assertGDFO(graph, 'a', 5)
206
self.assertGDFO(graph, 'c', 6)
209
class TestKnownGraphHeads(TestCaseWithKnownGraph):
211
scenarios = caching_scenarios() + non_caching_scenarios()
212
do_cache = None # Set by load_tests
214
def test_heads_null(self):
215
graph = self.make_known_graph(test_graph.ancestry_1)
216
self.assertEqual(set(['null:']), graph.heads(['null:']))
217
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
218
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
219
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
220
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
222
def test_heads_one(self):
223
# A single node will always be a head
224
graph = self.make_known_graph(test_graph.ancestry_1)
225
self.assertEqual(set(['null:']), graph.heads(['null:']))
226
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
227
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
228
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
229
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
230
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
232
def test_heads_single(self):
233
graph = self.make_known_graph(test_graph.ancestry_1)
234
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
235
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
236
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
237
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
238
self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
239
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
240
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
241
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
242
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
244
def test_heads_two_heads(self):
245
graph = self.make_known_graph(test_graph.ancestry_1)
246
self.assertEqual(set(['rev2a', 'rev2b']),
247
graph.heads(['rev2a', 'rev2b']))
248
self.assertEqual(set(['rev3', 'rev2b']),
249
graph.heads(['rev3', 'rev2b']))
251
def test_heads_criss_cross(self):
252
graph = self.make_known_graph(test_graph.criss_cross)
253
self.assertEqual(set(['rev2a']),
254
graph.heads(['rev2a', 'rev1']))
255
self.assertEqual(set(['rev2b']),
256
graph.heads(['rev2b', 'rev1']))
257
self.assertEqual(set(['rev3a']),
258
graph.heads(['rev3a', 'rev1']))
259
self.assertEqual(set(['rev3b']),
260
graph.heads(['rev3b', 'rev1']))
261
self.assertEqual(set(['rev2a', 'rev2b']),
262
graph.heads(['rev2a', 'rev2b']))
263
self.assertEqual(set(['rev3a']),
264
graph.heads(['rev3a', 'rev2a']))
265
self.assertEqual(set(['rev3a']),
266
graph.heads(['rev3a', 'rev2b']))
267
self.assertEqual(set(['rev3a']),
268
graph.heads(['rev3a', 'rev2a', 'rev2b']))
269
self.assertEqual(set(['rev3b']),
270
graph.heads(['rev3b', 'rev2a']))
271
self.assertEqual(set(['rev3b']),
272
graph.heads(['rev3b', 'rev2b']))
273
self.assertEqual(set(['rev3b']),
274
graph.heads(['rev3b', 'rev2a', 'rev2b']))
275
self.assertEqual(set(['rev3a', 'rev3b']),
276
graph.heads(['rev3a', 'rev3b']))
277
self.assertEqual(set(['rev3a', 'rev3b']),
278
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
280
def test_heads_shortcut(self):
281
graph = self.make_known_graph(test_graph.history_shortcut)
282
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
283
graph.heads(['rev2a', 'rev2b', 'rev2c']))
284
self.assertEqual(set(['rev3a', 'rev3b']),
285
graph.heads(['rev3a', 'rev3b']))
286
self.assertEqual(set(['rev3a', 'rev3b']),
287
graph.heads(['rev2a', 'rev3a', 'rev3b']))
288
self.assertEqual(set(['rev2a', 'rev3b']),
289
graph.heads(['rev2a', 'rev3b']))
290
self.assertEqual(set(['rev2c', 'rev3a']),
291
graph.heads(['rev2c', 'rev3a']))
293
def test_heads_linear(self):
294
graph = self.make_known_graph(test_graph.racing_shortcuts)
295
self.assertEqual(set(['w']), graph.heads(['w', 's']))
296
self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
297
self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
298
self.assertEqual(set(['z']), graph.heads(['s', 'z']))
300
def test_heads_alt_merge(self):
301
graph = self.make_known_graph(alt_merge)
302
self.assertEqual(set(['c']), graph.heads(['a', 'c']))
304
def test_heads_with_ghost(self):
305
graph = self.make_known_graph(test_graph.with_ghost)
306
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
307
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
308
self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
309
self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
310
self.assertEqual(set(['c']), graph.heads(['c', 'g']))
311
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
312
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
313
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
315
def test_filling_in_ghosts_resets_head_cache(self):
316
graph = self.make_known_graph(test_graph.with_ghost)
317
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
318
# 'g' is filled in, and decends from 'e', so the heads result is now
320
graph.add_node('g', ['e'])
321
self.assertEqual(set(['g']), graph.heads(['e', 'g']))
324
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
326
def assertTopoSortOrder(self, ancestry):
327
"""Check topo_sort and iter_topo_order is genuinely topological order.
329
For every child in the graph, check if it comes after all of it's
332
graph = self.make_known_graph(ancestry)
333
sort_result = graph.topo_sort()
334
# We should have an entry in sort_result for every entry present in the
336
self.assertEqual(len(ancestry), len(sort_result))
337
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
338
for node in sort_result:
339
parents = ancestry[node]
340
for parent in parents:
341
if parent not in ancestry:
344
if node_idx[node] <= node_idx[parent]:
345
self.fail("parent %s must come before child %s:\n%s"
346
% (parent, node, sort_result))
348
def test_topo_sort_empty(self):
349
"""TopoSort empty list"""
350
self.assertTopoSortOrder({})
352
def test_topo_sort_easy(self):
353
"""TopoSort list with one node"""
354
self.assertTopoSortOrder({0: []})
356
def test_topo_sort_cycle(self):
357
"""TopoSort traps graph with cycles"""
358
g = self.make_known_graph({0: [1],
360
self.assertRaises(errors.GraphCycleError, g.topo_sort)
362
def test_topo_sort_cycle_2(self):
363
"""TopoSort traps graph with longer cycle"""
364
g = self.make_known_graph({0: [1],
367
self.assertRaises(errors.GraphCycleError, g.topo_sort)
369
def test_topo_sort_cycle_with_tail(self):
370
"""TopoSort traps graph with longer cycle"""
371
g = self.make_known_graph({0: [1],
376
self.assertRaises(errors.GraphCycleError, g.topo_sort)
378
def test_topo_sort_1(self):
379
"""TopoSort simple nontrivial graph"""
380
self.assertTopoSortOrder({0: [3],
386
def test_topo_sort_partial(self):
387
"""Topological sort with partial ordering.
389
Multiple correct orderings are possible, so test for
390
correctness, not for exact match on the resulting list.
392
self.assertTopoSortOrder({0: [],
402
def test_topo_sort_ghost_parent(self):
403
"""Sort nodes, but don't include some parents in the output"""
404
self.assertTopoSortOrder({0: [1],
408
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
410
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
411
"""Check that merge based sorting and iter_topo_order on graph works."""
412
graph = self.make_known_graph(ancestry)
413
value = graph.merge_sort(branch_tip)
414
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
416
if result_list != value:
417
self.assertEqualDiff(pprint.pformat(result_list),
418
pprint.pformat(value))
420
def test_merge_sort_empty(self):
421
# sorting of an emptygraph does not error
422
self.assertSortAndIterate({}, None, [])
423
self.assertSortAndIterate({}, NULL_REVISION, [])
424
self.assertSortAndIterate({}, (NULL_REVISION,), [])
426
def test_merge_sort_not_empty_no_tip(self):
427
# merge sorting of a branch starting with None should result
428
# in an empty list: no revisions are dragged in.
429
self.assertSortAndIterate({0: []}, None, [])
430
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
431
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
433
def test_merge_sort_one_revision(self):
434
# sorting with one revision as the tip returns the correct fields:
435
# sequence - 0, revision id, merge depth - 0, end_of_merge
436
self.assertSortAndIterate({'id': []},
438
[('id', 0, (1,), True)])
440
def test_sequence_numbers_increase_no_merges(self):
441
# emit a few revisions with no merges to check the sequence
442
# numbering works in trivial cases
443
self.assertSortAndIterate(
448
[('C', 0, (3,), False),
449
('B', 0, (2,), False),
450
('A', 0, (1,), True),
454
def test_sequence_numbers_increase_with_merges(self):
455
# test that sequence numbers increase across merges
456
self.assertSortAndIterate(
461
[('C', 0, (2,), False),
462
('B', 1, (1,1,1), True),
463
('A', 0, (1,), True),
467
def test_merge_sort_race(self):
483
self.assertSortAndIterate(graph, 'F',
484
[('F', 0, (3,), False),
485
('D', 1, (2,2,1), False),
486
('C', 2, (2,1,1), True),
487
('B', 0, (2,), False),
488
('A', 0, (1,), True),
506
self.assertSortAndIterate(graph, 'F',
507
[('F', 0, (3,), False),
508
('D', 1, (2,1,2), False),
509
('C', 2, (2,2,1), True),
510
('X', 1, (2,1,1), True),
511
('B', 0, (2,), False),
512
('A', 0, (1,), True),
515
def test_merge_depth_with_nested_merges(self):
516
# the merge depth marker should reflect the depth of the revision
517
# in terms of merges out from the mainline
518
# revid, depth, parents:
527
self.assertSortAndIterate(
538
[('A', 0, (3,), False),
539
('B', 1, (1,3,2), False),
540
('C', 1, (1,3,1), True),
541
('D', 0, (2,), False),
542
('E', 1, (1,1,2), False),
543
('F', 2, (1,2,1), True),
544
('G', 1, (1,1,1), True),
545
('H', 0, (1,), True),
549
def test_dotted_revnos_with_simple_merges(self):
554
# D E F 3, 1.1.2, 1.2.1
556
# G H I 4, 1.2.2, 1.3.1
561
self.assertSortAndIterate(
576
[('L', 0, (6,), False),
577
('K', 1, (1,3,2), False),
578
('I', 1, (1,3,1), True),
579
('J', 0, (5,), False),
580
('H', 1, (1,2,2), False),
581
('F', 1, (1,2,1), True),
582
('G', 0, (4,), False),
583
('E', 1, (1,1,2), False),
584
('C', 1, (1,1,1), True),
585
('D', 0, (3,), False),
586
('B', 0, (2,), False),
587
('A', 0, (1,), True),
590
# Adding a shortcut from the first revision should not change any of
591
# the existing numbers
592
self.assertSortAndIterate(
609
[('N', 0, (7,), False),
610
('M', 1, (1,4,1), True),
611
('L', 0, (6,), False),
612
('K', 1, (1,3,2), False),
613
('I', 1, (1,3,1), True),
614
('J', 0, (5,), False),
615
('H', 1, (1,2,2), False),
616
('F', 1, (1,2,1), True),
617
('G', 0, (4,), False),
618
('E', 1, (1,1,2), False),
619
('C', 1, (1,1,1), True),
620
('D', 0, (3,), False),
621
('B', 0, (2,), False),
622
('A', 0, (1,), True),
626
def test_end_of_merge_not_last_revision_in_branch(self):
627
# within a branch only the last revision gets an
628
# end of merge marker.
629
self.assertSortAndIterate(
634
[('A', 0, (2,), False),
639
def test_end_of_merge_multiple_revisions_merged_at_once(self):
640
# when multiple branches are merged at once, both of their
641
# branch-endpoints should be listed as end-of-merge.
642
# Also, the order of the multiple merges should be
643
# left-right shown top to bottom.
644
# * means end of merge
653
self.assertSortAndIterate(
654
{'A': ['H', 'B', 'E'],
664
[('A', 0, (2,), False),
665
('B', 1, (1,3,2), False),
666
('C', 2, (1,4,1), True),
667
('D', 1, (1,3,1), True),
668
('E', 1, (1,1,2), False),
669
('F', 2, (1,2,1), True),
670
('G', 1, (1,1,1), True),
671
('H', 0, (1,), True),
675
def test_parallel_root_sequence_numbers_increase_with_merges(self):
676
"""When there are parallel roots, check their revnos."""
677
self.assertSortAndIterate(
682
[('C', 0, (2,), False),
683
('B', 1, (0,1,1), True),
684
('A', 0, (1,), True),
688
def test_revnos_are_globally_assigned(self):
689
"""revnos are assigned according to the revision they derive from."""
690
# in this test we setup a number of branches that all derive from
691
# the first revision, and then merge them one at a time, which
692
# should give the revisions as they merge numbers still deriving from
693
# the revision were based on.
694
# merge 3: J: ['G', 'I']
698
# merge 2: G: ['D', 'F']
702
# merge 1: D: ['A', 'C']
707
self.assertSortAndIterate(
720
[('J', 0, (4,), False),
721
('I', 1, (1,3,2), False),
722
('H', 1, (1,3,1), True),
723
('G', 0, (3,), False),
724
('F', 1, (1,2,2), False),
725
('E', 1, (1,2,1), True),
726
('D', 0, (2,), False),
727
('C', 1, (1,1,2), False),
728
('B', 1, (1,1,1), True),
729
('A', 0, (1,), True),
733
def test_roots_and_sub_branches_versus_ghosts(self):
734
"""Extra roots and their mini branches use the same numbering.
736
All of them use the 0-node numbering.
749
self.assertSortAndIterate(
770
[('R', 0, (6,), False),
771
('Q', 1, (0,4,5), False),
772
('P', 2, (0,6,1), True),
773
('O', 1, (0,4,4), False),
774
('N', 1, (0,4,3), False),
775
('M', 2, (0,5,1), True),
776
('L', 1, (0,4,2), False),
777
('K', 1, (0,4,1), True),
778
('J', 0, (5,), False),
779
('I', 1, (0,3,1), True),
780
('H', 0, (4,), False),
781
('G', 1, (0,1,3), False),
782
('F', 2, (0,2,1), True),
783
('E', 1, (0,1,2), False),
784
('D', 1, (0,1,1), True),
785
('C', 0, (3,), False),
786
('B', 0, (2,), False),
787
('A', 0, (1,), True),
791
def test_ghost(self):
792
# merge_sort should be able to ignore ghosts
798
self.assertSortAndIterate(
804
[('C', 0, (3,), False),
805
('B', 0, (2,), False),
806
('A', 0, (1,), True),
809
def test_lefthand_ghost(self):
815
self.assertSortAndIterate(
819
[('B', 0, (2,), False),
820
('A', 0, (1,), True),
823
def test_graph_cycle(self):
824
# merge_sort should fail with a simple error when a graph cycle is
836
self.assertRaises(errors.GraphCycleError,
837
self.assertSortAndIterate,
848
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
849
"""Test the sort order returned by gc_sort."""
851
def assertSorted(self, expected, parent_map):
852
graph = self.make_known_graph(parent_map)
853
value = graph.gc_sort()
854
if expected != value:
855
self.assertEqualDiff(pprint.pformat(expected),
856
pprint.pformat(value))
858
def test_empty(self):
859
self.assertSorted([], {})
861
def test_single(self):
862
self.assertSorted(['a'], {'a':()})
863
self.assertSorted([('a',)], {('a',):()})
864
self.assertSorted([('F', 'a')], {('F', 'a'):()})
866
def test_linear(self):
867
self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
868
self.assertSorted([('c',), ('b',), ('a',)],
869
{('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
870
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
871
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
872
('F', 'c'): (('F', 'b'),)})
874
def test_mixed_ancestries(self):
875
# Each prefix should be sorted separately
876
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
877
('G', 'c'), ('G', 'b'), ('G', 'a'),
878
('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
880
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
881
('F', 'c'): (('F', 'b'),),
882
('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
883
('G', 'c'): (('G', 'b'),),
884
('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
885
('Q', 'c'): (('Q', 'b'),),
888
def test_stable_sorting(self):
889
# the sort order should be stable even when extra nodes are added
890
self.assertSorted(['b', 'c', 'a'],
891
{'a':(), 'b':('a',), 'c':('a',)})
892
self.assertSorted(['b', 'c', 'd', 'a'],
893
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
894
self.assertSorted(['b', 'c', 'd', 'a'],
895
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
896
self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
897
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
899
self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
900
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
906
def test_skip_ghost(self):
907
self.assertSorted(['b', 'c', 'a'],
908
{'a':(), 'b':('a', 'ghost'), 'c':('a',)})
910
def test_skip_mainline_ghost(self):
911
self.assertSorted(['b', 'c', 'a'],
912
{'a':(), 'b':('ghost', 'a'), 'c':('a',)})
added
removed
bzrlib/tests/test__known_graph.py
