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
29
from bzrlib.tests import (
34
def caching_scenarios():
36
('python', {'module': _known_graph_py, 'do_cache': True}),
38
if compiled_known_graph_feature.available():
39
scenarios.append(('C', {'module': compiled_known_graph_feature.module,
44
def non_caching_scenarios():
46
('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
48
if compiled_known_graph_feature.available():
50
('C-nocache', {'module': compiled_known_graph_feature.module,
55
load_tests = load_tests_apply_scenarios
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
59
'bzrlib._known_graph_pyx')
69
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
72
class TestCaseWithKnownGraph(tests.TestCase):
74
scenarios = caching_scenarios()
75
module = None # Set by load_tests
77
def make_known_graph(self, ancestry):
78
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
81
class TestKnownGraph(TestCaseWithKnownGraph):
83
def assertGDFO(self, graph, rev, gdfo):
84
node = graph._nodes[rev]
85
self.assertEqual(gdfo, node.gdfo)
87
def test_children_ancestry1(self):
88
graph = self.make_known_graph(test_graph.ancestry_1)
89
self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
90
self.assertEqual(['rev2a', 'rev2b'],
91
sorted(graph.get_child_keys('rev1')))
92
self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
93
self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
94
self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
95
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
97
def test_parent_ancestry1(self):
98
graph = self.make_known_graph(test_graph.ancestry_1)
99
self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
100
self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
101
self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
102
self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
103
self.assertEqual(['rev2b', 'rev3'],
104
sorted(graph.get_parent_keys('rev4')))
105
self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
107
def test_parent_with_ghost(self):
108
graph = self.make_known_graph(test_graph.with_ghost)
109
self.assertEqual(None, graph.get_parent_keys('g'))
111
def test_gdfo_ancestry_1(self):
112
graph = self.make_known_graph(test_graph.ancestry_1)
113
self.assertGDFO(graph, 'rev1', 2)
114
self.assertGDFO(graph, 'rev2b', 3)
115
self.assertGDFO(graph, 'rev2a', 3)
116
self.assertGDFO(graph, 'rev3', 4)
117
self.assertGDFO(graph, 'rev4', 5)
119
def test_gdfo_feature_branch(self):
120
graph = self.make_known_graph(test_graph.feature_branch)
121
self.assertGDFO(graph, 'rev1', 2)
122
self.assertGDFO(graph, 'rev2b', 3)
123
self.assertGDFO(graph, 'rev3b', 4)
125
def test_gdfo_extended_history_shortcut(self):
126
graph = self.make_known_graph(test_graph.extended_history_shortcut)
127
self.assertGDFO(graph, 'a', 2)
128
self.assertGDFO(graph, 'b', 3)
129
self.assertGDFO(graph, 'c', 4)
130
self.assertGDFO(graph, 'd', 5)
131
self.assertGDFO(graph, 'e', 6)
132
self.assertGDFO(graph, 'f', 6)
134
def test_gdfo_with_ghost(self):
135
graph = self.make_known_graph(test_graph.with_ghost)
136
self.assertGDFO(graph, 'f', 2)
137
self.assertGDFO(graph, 'e', 3)
138
self.assertGDFO(graph, 'g', 1)
139
self.assertGDFO(graph, 'b', 4)
140
self.assertGDFO(graph, 'd', 4)
141
self.assertGDFO(graph, 'a', 5)
142
self.assertGDFO(graph, 'c', 5)
144
def test_add_existing_node(self):
145
graph = self.make_known_graph(test_graph.ancestry_1)
146
# Add a node that already exists with identical content
148
self.assertGDFO(graph, 'rev4', 5)
149
graph.add_node('rev4', ['rev3', 'rev2b'])
150
self.assertGDFO(graph, 'rev4', 5)
151
# This also works if we use a tuple rather than a list
152
graph.add_node('rev4', ('rev3', 'rev2b'))
154
def test_add_existing_node_mismatched_parents(self):
155
graph = self.make_known_graph(test_graph.ancestry_1)
156
self.assertRaises(ValueError, graph.add_node, 'rev4',
159
def test_add_node_with_ghost_parent(self):
160
graph = self.make_known_graph(test_graph.ancestry_1)
161
graph.add_node('rev5', ['rev2b', 'revGhost'])
162
self.assertGDFO(graph, 'rev5', 4)
163
self.assertGDFO(graph, 'revGhost', 1)
165
def test_add_new_root(self):
166
graph = self.make_known_graph(test_graph.ancestry_1)
167
graph.add_node('rev5', [])
168
self.assertGDFO(graph, 'rev5', 1)
170
def test_add_with_all_ghost_parents(self):
171
graph = self.make_known_graph(test_graph.ancestry_1)
172
graph.add_node('rev5', ['ghost'])
173
self.assertGDFO(graph, 'rev5', 2)
174
self.assertGDFO(graph, 'ghost', 1)
176
def test_gdfo_after_add_node(self):
177
graph = self.make_known_graph(test_graph.ancestry_1)
178
self.assertEqual([], graph.get_child_keys('rev4'))
179
graph.add_node('rev5', ['rev4'])
180
self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
181
self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
182
self.assertEqual([], graph.get_child_keys('rev5'))
183
self.assertGDFO(graph, 'rev5', 6)
184
graph.add_node('rev6', ['rev2b'])
185
graph.add_node('rev7', ['rev6'])
186
graph.add_node('rev8', ['rev7', 'rev5'])
187
self.assertGDFO(graph, 'rev5', 6)
188
self.assertGDFO(graph, 'rev6', 4)
189
self.assertGDFO(graph, 'rev7', 5)
190
self.assertGDFO(graph, 'rev8', 7)
192
def test_fill_in_ghost(self):
193
graph = self.make_known_graph(test_graph.with_ghost)
194
# Add in a couple nodes and then fill in the 'ghost' so that it should
195
# cause renumbering of children nodes
196
graph.add_node('x', [])
197
graph.add_node('y', ['x'])
198
graph.add_node('z', ['y'])
199
graph.add_node('g', ['z'])
200
self.assertGDFO(graph, 'f', 2)
201
self.assertGDFO(graph, 'e', 3)
202
self.assertGDFO(graph, 'x', 1)
203
self.assertGDFO(graph, 'y', 2)
204
self.assertGDFO(graph, 'z', 3)
205
self.assertGDFO(graph, 'g', 4)
206
self.assertGDFO(graph, 'b', 4)
207
self.assertGDFO(graph, 'd', 5)
208
self.assertGDFO(graph, 'a', 5)
209
self.assertGDFO(graph, 'c', 6)
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
214
scenarios = caching_scenarios() + non_caching_scenarios()
215
do_cache = None # Set by load_tests
217
def test_heads_null(self):
218
graph = self.make_known_graph(test_graph.ancestry_1)
219
self.assertEqual(set(['null:']), graph.heads(['null:']))
220
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
221
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
222
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
223
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
225
def test_heads_one(self):
226
# A single node will always be a head
227
graph = self.make_known_graph(test_graph.ancestry_1)
228
self.assertEqual(set(['null:']), graph.heads(['null:']))
229
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
230
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
231
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
232
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
233
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
235
def test_heads_single(self):
236
graph = self.make_known_graph(test_graph.ancestry_1)
237
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
238
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
239
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
240
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
241
self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
242
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
243
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
244
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
245
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
247
def test_heads_two_heads(self):
248
graph = self.make_known_graph(test_graph.ancestry_1)
249
self.assertEqual(set(['rev2a', 'rev2b']),
250
graph.heads(['rev2a', 'rev2b']))
251
self.assertEqual(set(['rev3', 'rev2b']),
252
graph.heads(['rev3', 'rev2b']))
254
def test_heads_criss_cross(self):
255
graph = self.make_known_graph(test_graph.criss_cross)
256
self.assertEqual(set(['rev2a']),
257
graph.heads(['rev2a', 'rev1']))
258
self.assertEqual(set(['rev2b']),
259
graph.heads(['rev2b', 'rev1']))
260
self.assertEqual(set(['rev3a']),
261
graph.heads(['rev3a', 'rev1']))
262
self.assertEqual(set(['rev3b']),
263
graph.heads(['rev3b', 'rev1']))
264
self.assertEqual(set(['rev2a', 'rev2b']),
265
graph.heads(['rev2a', 'rev2b']))
266
self.assertEqual(set(['rev3a']),
267
graph.heads(['rev3a', 'rev2a']))
268
self.assertEqual(set(['rev3a']),
269
graph.heads(['rev3a', 'rev2b']))
270
self.assertEqual(set(['rev3a']),
271
graph.heads(['rev3a', 'rev2a', 'rev2b']))
272
self.assertEqual(set(['rev3b']),
273
graph.heads(['rev3b', 'rev2a']))
274
self.assertEqual(set(['rev3b']),
275
graph.heads(['rev3b', 'rev2b']))
276
self.assertEqual(set(['rev3b']),
277
graph.heads(['rev3b', 'rev2a', 'rev2b']))
278
self.assertEqual(set(['rev3a', 'rev3b']),
279
graph.heads(['rev3a', 'rev3b']))
280
self.assertEqual(set(['rev3a', 'rev3b']),
281
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
283
def test_heads_shortcut(self):
284
graph = self.make_known_graph(test_graph.history_shortcut)
285
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
286
graph.heads(['rev2a', 'rev2b', 'rev2c']))
287
self.assertEqual(set(['rev3a', 'rev3b']),
288
graph.heads(['rev3a', 'rev3b']))
289
self.assertEqual(set(['rev3a', 'rev3b']),
290
graph.heads(['rev2a', 'rev3a', 'rev3b']))
291
self.assertEqual(set(['rev2a', 'rev3b']),
292
graph.heads(['rev2a', 'rev3b']))
293
self.assertEqual(set(['rev2c', 'rev3a']),
294
graph.heads(['rev2c', 'rev3a']))
296
def test_heads_linear(self):
297
graph = self.make_known_graph(test_graph.racing_shortcuts)
298
self.assertEqual(set(['w']), graph.heads(['w', 's']))
299
self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
300
self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
301
self.assertEqual(set(['z']), graph.heads(['s', 'z']))
303
def test_heads_alt_merge(self):
304
graph = self.make_known_graph(alt_merge)
305
self.assertEqual(set(['c']), graph.heads(['a', 'c']))
307
def test_heads_with_ghost(self):
308
graph = self.make_known_graph(test_graph.with_ghost)
309
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
310
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
311
self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
312
self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
313
self.assertEqual(set(['c']), graph.heads(['c', 'g']))
314
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
315
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
316
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
318
def test_filling_in_ghosts_resets_head_cache(self):
319
graph = self.make_known_graph(test_graph.with_ghost)
320
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
321
# 'g' is filled in, and decends from 'e', so the heads result is now
323
graph.add_node('g', ['e'])
324
self.assertEqual(set(['g']), graph.heads(['e', 'g']))
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
329
def assertTopoSortOrder(self, ancestry):
330
"""Check topo_sort and iter_topo_order is genuinely topological order.
332
For every child in the graph, check if it comes after all of it's
335
graph = self.make_known_graph(ancestry)
336
sort_result = graph.topo_sort()
337
# We should have an entry in sort_result for every entry present in the
339
self.assertEqual(len(ancestry), len(sort_result))
340
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
341
for node in sort_result:
342
parents = ancestry[node]
343
for parent in parents:
344
if parent not in ancestry:
347
if node_idx[node] <= node_idx[parent]:
348
self.fail("parent %s must come before child %s:\n%s"
349
% (parent, node, sort_result))
351
def test_topo_sort_empty(self):
352
"""TopoSort empty list"""
353
self.assertTopoSortOrder({})
355
def test_topo_sort_easy(self):
356
"""TopoSort list with one node"""
357
self.assertTopoSortOrder({0: []})
359
def test_topo_sort_cycle(self):
360
"""TopoSort traps graph with cycles"""
361
g = self.make_known_graph({0: [1],
363
self.assertRaises(errors.GraphCycleError, g.topo_sort)
365
def test_topo_sort_cycle_2(self):
366
"""TopoSort traps graph with longer cycle"""
367
g = self.make_known_graph({0: [1],
370
self.assertRaises(errors.GraphCycleError, g.topo_sort)
372
def test_topo_sort_cycle_with_tail(self):
373
"""TopoSort traps graph with longer cycle"""
374
g = self.make_known_graph({0: [1],
379
self.assertRaises(errors.GraphCycleError, g.topo_sort)
381
def test_topo_sort_1(self):
382
"""TopoSort simple nontrivial graph"""
383
self.assertTopoSortOrder({0: [3],
389
def test_topo_sort_partial(self):
390
"""Topological sort with partial ordering.
392
Multiple correct orderings are possible, so test for
393
correctness, not for exact match on the resulting list.
395
self.assertTopoSortOrder({0: [],
405
def test_topo_sort_ghost_parent(self):
406
"""Sort nodes, but don't include some parents in the output"""
407
self.assertTopoSortOrder({0: [1],
411
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
413
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
414
"""Check that merge based sorting and iter_topo_order on graph works."""
415
graph = self.make_known_graph(ancestry)
416
value = graph.merge_sort(branch_tip)
417
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
419
if result_list != value:
420
self.assertEqualDiff(pprint.pformat(result_list),
421
pprint.pformat(value))
423
def test_merge_sort_empty(self):
424
# sorting of an emptygraph does not error
425
self.assertSortAndIterate({}, None, [])
426
self.assertSortAndIterate({}, NULL_REVISION, [])
427
self.assertSortAndIterate({}, (NULL_REVISION,), [])
429
def test_merge_sort_not_empty_no_tip(self):
430
# merge sorting of a branch starting with None should result
431
# in an empty list: no revisions are dragged in.
432
self.assertSortAndIterate({0: []}, None, [])
433
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
434
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
436
def test_merge_sort_one_revision(self):
437
# sorting with one revision as the tip returns the correct fields:
438
# sequence - 0, revision id, merge depth - 0, end_of_merge
439
self.assertSortAndIterate({'id': []},
441
[('id', 0, (1,), True)])
443
def test_sequence_numbers_increase_no_merges(self):
444
# emit a few revisions with no merges to check the sequence
445
# numbering works in trivial cases
446
self.assertSortAndIterate(
451
[('C', 0, (3,), False),
452
('B', 0, (2,), False),
453
('A', 0, (1,), True),
457
def test_sequence_numbers_increase_with_merges(self):
458
# test that sequence numbers increase across merges
459
self.assertSortAndIterate(
464
[('C', 0, (2,), False),
465
('B', 1, (1,1,1), True),
466
('A', 0, (1,), True),
470
def test_merge_sort_race(self):
486
self.assertSortAndIterate(graph, 'F',
487
[('F', 0, (3,), False),
488
('D', 1, (2,2,1), False),
489
('C', 2, (2,1,1), True),
490
('B', 0, (2,), False),
491
('A', 0, (1,), True),
509
self.assertSortAndIterate(graph, 'F',
510
[('F', 0, (3,), False),
511
('D', 1, (2,1,2), False),
512
('C', 2, (2,2,1), True),
513
('X', 1, (2,1,1), True),
514
('B', 0, (2,), False),
515
('A', 0, (1,), True),
518
def test_merge_depth_with_nested_merges(self):
519
# the merge depth marker should reflect the depth of the revision
520
# in terms of merges out from the mainline
521
# revid, depth, parents:
530
self.assertSortAndIterate(
541
[('A', 0, (3,), False),
542
('B', 1, (1,3,2), False),
543
('C', 1, (1,3,1), True),
544
('D', 0, (2,), False),
545
('E', 1, (1,1,2), False),
546
('F', 2, (1,2,1), True),
547
('G', 1, (1,1,1), True),
548
('H', 0, (1,), True),
552
def test_dotted_revnos_with_simple_merges(self):
557
# D E F 3, 1.1.2, 1.2.1
559
# G H I 4, 1.2.2, 1.3.1
564
self.assertSortAndIterate(
579
[('L', 0, (6,), False),
580
('K', 1, (1,3,2), False),
581
('I', 1, (1,3,1), True),
582
('J', 0, (5,), False),
583
('H', 1, (1,2,2), False),
584
('F', 1, (1,2,1), True),
585
('G', 0, (4,), False),
586
('E', 1, (1,1,2), False),
587
('C', 1, (1,1,1), True),
588
('D', 0, (3,), False),
589
('B', 0, (2,), False),
590
('A', 0, (1,), True),
593
# Adding a shortcut from the first revision should not change any of
594
# the existing numbers
595
self.assertSortAndIterate(
612
[('N', 0, (7,), False),
613
('M', 1, (1,4,1), True),
614
('L', 0, (6,), False),
615
('K', 1, (1,3,2), False),
616
('I', 1, (1,3,1), True),
617
('J', 0, (5,), False),
618
('H', 1, (1,2,2), False),
619
('F', 1, (1,2,1), True),
620
('G', 0, (4,), False),
621
('E', 1, (1,1,2), False),
622
('C', 1, (1,1,1), True),
623
('D', 0, (3,), False),
624
('B', 0, (2,), False),
625
('A', 0, (1,), True),
629
def test_end_of_merge_not_last_revision_in_branch(self):
630
# within a branch only the last revision gets an
631
# end of merge marker.
632
self.assertSortAndIterate(
637
[('A', 0, (2,), False),
642
def test_end_of_merge_multiple_revisions_merged_at_once(self):
643
# when multiple branches are merged at once, both of their
644
# branch-endpoints should be listed as end-of-merge.
645
# Also, the order of the multiple merges should be
646
# left-right shown top to bottom.
647
# * means end of merge
656
self.assertSortAndIterate(
657
{'A': ['H', 'B', 'E'],
667
[('A', 0, (2,), False),
668
('B', 1, (1,3,2), False),
669
('C', 2, (1,4,1), True),
670
('D', 1, (1,3,1), True),
671
('E', 1, (1,1,2), False),
672
('F', 2, (1,2,1), True),
673
('G', 1, (1,1,1), True),
674
('H', 0, (1,), True),
678
def test_parallel_root_sequence_numbers_increase_with_merges(self):
679
"""When there are parallel roots, check their revnos."""
680
self.assertSortAndIterate(
685
[('C', 0, (2,), False),
686
('B', 1, (0,1,1), True),
687
('A', 0, (1,), True),
691
def test_revnos_are_globally_assigned(self):
692
"""revnos are assigned according to the revision they derive from."""
693
# in this test we setup a number of branches that all derive from
694
# the first revision, and then merge them one at a time, which
695
# should give the revisions as they merge numbers still deriving from
696
# the revision were based on.
697
# merge 3: J: ['G', 'I']
701
# merge 2: G: ['D', 'F']
705
# merge 1: D: ['A', 'C']
710
self.assertSortAndIterate(
723
[('J', 0, (4,), False),
724
('I', 1, (1,3,2), False),
725
('H', 1, (1,3,1), True),
726
('G', 0, (3,), False),
727
('F', 1, (1,2,2), False),
728
('E', 1, (1,2,1), True),
729
('D', 0, (2,), False),
730
('C', 1, (1,1,2), False),
731
('B', 1, (1,1,1), True),
732
('A', 0, (1,), True),
736
def test_roots_and_sub_branches_versus_ghosts(self):
737
"""Extra roots and their mini branches use the same numbering.
739
All of them use the 0-node numbering.
752
self.assertSortAndIterate(
773
[('R', 0, (6,), False),
774
('Q', 1, (0,4,5), False),
775
('P', 2, (0,6,1), True),
776
('O', 1, (0,4,4), False),
777
('N', 1, (0,4,3), False),
778
('M', 2, (0,5,1), True),
779
('L', 1, (0,4,2), False),
780
('K', 1, (0,4,1), True),
781
('J', 0, (5,), False),
782
('I', 1, (0,3,1), True),
783
('H', 0, (4,), False),
784
('G', 1, (0,1,3), False),
785
('F', 2, (0,2,1), True),
786
('E', 1, (0,1,2), False),
787
('D', 1, (0,1,1), True),
788
('C', 0, (3,), False),
789
('B', 0, (2,), False),
790
('A', 0, (1,), True),
794
def test_ghost(self):
795
# merge_sort should be able to ignore ghosts
801
self.assertSortAndIterate(
807
[('C', 0, (3,), False),
808
('B', 0, (2,), False),
809
('A', 0, (1,), True),
812
def test_lefthand_ghost(self):
818
self.assertSortAndIterate(
822
[('B', 0, (2,), False),
823
('A', 0, (1,), True),
826
def test_graph_cycle(self):
827
# merge_sort should fail with a simple error when a graph cycle is
839
self.assertRaises(errors.GraphCycleError,
840
self.assertSortAndIterate,
851
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
852
"""Test the sort order returned by gc_sort."""
854
def assertSorted(self, expected, parent_map):
855
graph = self.make_known_graph(parent_map)
856
value = graph.gc_sort()
857
if expected != value:
858
self.assertEqualDiff(pprint.pformat(expected),
859
pprint.pformat(value))
861
def test_empty(self):
862
self.assertSorted([], {})
864
def test_single(self):
865
self.assertSorted(['a'], {'a':()})
866
self.assertSorted([('a',)], {('a',):()})
867
self.assertSorted([('F', 'a')], {('F', 'a'):()})
869
def test_linear(self):
870
self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
871
self.assertSorted([('c',), ('b',), ('a',)],
872
{('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
873
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
874
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
875
('F', 'c'): (('F', 'b'),)})
877
def test_mixed_ancestries(self):
878
# Each prefix should be sorted separately
879
self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
880
('G', 'c'), ('G', 'b'), ('G', 'a'),
881
('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
883
{('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
884
('F', 'c'): (('F', 'b'),),
885
('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
886
('G', 'c'): (('G', 'b'),),
887
('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
888
('Q', 'c'): (('Q', 'b'),),
891
def test_stable_sorting(self):
892
# the sort order should be stable even when extra nodes are added
893
self.assertSorted(['b', 'c', 'a'],
894
{'a':(), 'b':('a',), 'c':('a',)})
895
self.assertSorted(['b', 'c', 'd', 'a'],
896
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
897
self.assertSorted(['b', 'c', 'd', 'a'],
898
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
899
self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
900
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
902
self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
903
{'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
909
def test_skip_ghost(self):
910
self.assertSorted(['b', 'c', 'a'],
911
{'a':(), 'b':('a', 'ghost'), 'c':('a',)})
913
def test_skip_mainline_ghost(self):
914
self.assertSorted(['b', 'c', 'a'],
915
{'a':(), 'b':('ghost', 'a'), 'c':('a',)})
added
removed
bzrlib/tests/test__known_graph.py
