1
# Copyright (C) 2005 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
"""Tests for topological sort."""
21
from bzrlib.tests import TestCase
22
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
23
from bzrlib.errors import GraphCycleError
24
from bzrlib.revision import NULL_REVISION
27
class TopoSortTests(TestCase):
29
def assertSortAndIterate(self, graph, result_list):
30
"""Check that sorting and iter_topo_order on graph works."""
31
self.assertEquals(result_list, topo_sort(graph))
32
self.assertEqual(result_list,
33
list(TopoSorter(graph).iter_topo_order()))
35
def assertSortAndIterateRaise(self, exception_type, graph):
36
"""Try both iterating and topo_sorting graph and expect an exception."""
37
self.assertRaises(exception_type, topo_sort, graph)
38
self.assertRaises(exception_type,
40
TopoSorter(graph).iter_topo_order())
42
def test_tsort_empty(self):
43
"""TopoSort empty list"""
44
self.assertSortAndIterate([], [])
46
def test_tsort_easy(self):
47
"""TopoSort list with one node"""
48
self.assertSortAndIterate({0: []}.items(), [0])
50
def test_tsort_cycle(self):
51
"""TopoSort traps graph with cycles"""
52
self.assertSortAndIterateRaise(GraphCycleError,
56
def test_tsort_cycle_2(self):
57
"""TopoSort traps graph with longer cycle"""
58
self.assertSortAndIterateRaise(GraphCycleError,
63
def test_tsort_1(self):
64
"""TopoSort simple nontrivial graph"""
65
self.assertSortAndIterate({0: [3],
72
def test_tsort_partial(self):
73
"""Topological sort with partial ordering.
75
If the graph does not give an order between two nodes, they are
76
returned in lexicographical order.
78
self.assertSortAndIterate(([(0, []),
86
(8, [0, 1, 4, 5, 6])]),
87
[0, 1, 2, 3, 4, 5, 6, 7, 8])
89
def test_tsort_unincluded_parent(self):
90
"""Sort nodes, but don't include some parents in the output"""
91
self.assertSortAndIterate([(0, [1]),
96
class MergeSortTests(TestCase):
98
def assertSortAndIterate(self, graph, branch_tip, result_list,
99
generate_revno, mainline_revisions=None):
100
"""Check that merge based sorting and iter_topo_order on graph works."""
101
value = merge_sort(graph, branch_tip,
102
mainline_revisions=mainline_revisions,
103
generate_revno=generate_revno)
104
if result_list != value:
106
self.assertEqualDiff(pprint.pformat(result_list),
107
pprint.pformat(value))
108
self.assertEquals(result_list,
109
merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
110
generate_revno=generate_revno))
111
self.assertEqual(result_list,
115
mainline_revisions=mainline_revisions,
116
generate_revno=generate_revno,
117
).iter_topo_order()))
119
def test_merge_sort_empty(self):
120
# sorting of an emptygraph does not error
121
self.assertSortAndIterate({}, None, [], False)
122
self.assertSortAndIterate({}, None, [], True)
123
self.assertSortAndIterate({}, NULL_REVISION, [], False)
124
self.assertSortAndIterate({}, NULL_REVISION, [], True)
126
def test_merge_sort_not_empty_no_tip(self):
127
# merge sorting of a branch starting with None should result
128
# in an empty list: no revisions are dragged in.
129
self.assertSortAndIterate({0: []}.items(), None, [], False)
130
self.assertSortAndIterate({0: []}.items(), None, [], True)
132
def test_merge_sort_one_revision(self):
133
# sorting with one revision as the tip returns the correct fields:
134
# sequence - 0, revision id, merge depth - 0, end_of_merge
135
self.assertSortAndIterate({'id': []}.items(),
137
[(0, 'id', 0, True)],
139
self.assertSortAndIterate({'id': []}.items(),
141
[(0, 'id', 0, (1,), True)],
144
def test_sequence_numbers_increase_no_merges(self):
145
# emit a few revisions with no merges to check the sequence
146
# numbering works in trivial cases
147
self.assertSortAndIterate(
158
self.assertSortAndIterate(
163
[(0, 'C', 0, (3,), False),
164
(1, 'B', 0, (2,), False),
165
(2, 'A', 0, (1,), True),
170
def test_sequence_numbers_increase_with_merges(self):
171
# test that sequence numbers increase across merges
172
self.assertSortAndIterate(
175
'C': ['A', 'B']}.items(),
183
self.assertSortAndIterate(
186
'C': ['A', 'B']}.items(),
188
[(0, 'C', 0, (2,), False),
189
(1, 'B', 1, (1,1,1), True),
190
(2, 'A', 0, (1,), True),
195
def test_merge_sort_race(self):
211
self.assertSortAndIterate(graph, 'F',
212
[(0, 'F', 0, (3,), False),
213
(1, 'D', 1, (2,2,1), False),
214
(2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
215
(3, 'B', 0, (2,), False),
216
(4, 'A', 0, (1,), True),
234
self.assertSortAndIterate(graph, 'F',
235
[(0, 'F', 0, (3,), False),
236
(1, 'D', 1, (2,1,2), False),
237
(2, 'C', 2, (2,2,1), True),
238
(3, 'X', 1, (2,1,1), True),
239
(4, 'B', 0, (2,), False),
240
(5, 'A', 0, (1,), True),
243
def test_merge_depth_with_nested_merges(self):
244
# the merge depth marker should reflect the depth of the revision
245
# in terms of merges out from the mainline
246
# revid, depth, parents:
255
self.assertSortAndIterate(
277
self.assertSortAndIterate(
288
[(0, 'A', 0, (3,), False),
289
(1, 'B', 1, (1,3,2), False),
290
(2, 'C', 1, (1,3,1), True),
291
(3, 'D', 0, (2,), False),
292
(4, 'E', 1, (1,1,2), False),
293
(5, 'F', 2, (1,2,1), True),
294
(6, 'G', 1, (1,1,1), True),
295
(7, 'H', 0, (1,), True),
300
def test_dotted_revnos_with_simple_merges(self):
305
# D E F 3, 1.1.2, 1.2.1
307
# G H I 4, 1.2.2, 1.3.1
312
self.assertSortAndIterate(
327
[(0, 'L', 0, (6,), False),
328
(1, 'K', 1, (1,3,2), False),
329
(2, 'I', 1, (1,3,1), True),
330
(3, 'J', 0, (5,), False),
331
(4, 'H', 1, (1,2,2), False),
332
(5, 'F', 1, (1,2,1), True),
333
(6, 'G', 0, (4,), False),
334
(7, 'E', 1, (1,1,2), False),
335
(8, 'C', 1, (1,1,1), True),
336
(9, 'D', 0, (3,), False),
337
(10, 'B', 0, (2,), False),
338
(11, 'A', 0, (1,), True),
342
# Adding a shortcut from the first revision should not change any of
343
# the existing numbers
344
self.assertSortAndIterate(
361
[(0, 'N', 0, (7,), False),
362
(1, 'M', 1, (1,4,1), True),
363
(2, 'L', 0, (6,), False),
364
(3, 'K', 1, (1,3,2), False),
365
(4, 'I', 1, (1,3,1), True),
366
(5, 'J', 0, (5,), False),
367
(6, 'H', 1, (1,2,2), False),
368
(7, 'F', 1, (1,2,1), True),
369
(8, 'G', 0, (4,), False),
370
(9, 'E', 1, (1,1,2), False),
371
(10, 'C', 1, (1,1,1), True),
372
(11, 'D', 0, (3,), False),
373
(12, 'B', 0, (2,), False),
374
(13, 'A', 0, (1,), True),
379
def test_end_of_merge_not_last_revision_in_branch(self):
380
# within a branch only the last revision gets an
381
# end of merge marker.
382
self.assertSortAndIterate(
392
self.assertSortAndIterate(
397
[(0, 'A', 0, (2,), False),
398
(1, 'B', 0, (1,), True)
403
def test_end_of_merge_multiple_revisions_merged_at_once(self):
404
# when multiple branches are merged at once, both of their
405
# branch-endpoints should be listed as end-of-merge.
406
# Also, the order of the multiple merges should be
407
# left-right shown top to bottom.
408
# * means end of merge
417
self.assertSortAndIterate(
418
{'A': ['H', 'B', 'E'],
439
self.assertSortAndIterate(
440
{'A': ['H', 'B', 'E'],
450
[(0, 'A', 0, (2,), False),
451
(1, 'B', 1, (1,3,2), False),
452
(2, 'C', 2, (1,4,1), True),
453
(3, 'D', 1, (1,3,1), True),
454
(4, 'E', 1, (1,1,2), False),
455
(5, 'F', 2, (1,2,1), True),
456
(6, 'G', 1, (1,1,1), True),
457
(7, 'H', 0, (1,), True),
462
def test_mainline_revs_partial(self):
463
# when a mainline_revisions list is passed this must
464
# override the graphs idea of mainline, and must also
465
# truncate the output to the specified range, if needed.
466
# so we test both at once: a mainline_revisions list that
467
# disagrees with the graph about which revs are 'mainline'
468
# and also truncates the output.
475
# with a mainline of NONE,E,A (the inferred one) this will show the merge
477
# with a overriden mainline of NONE,E,D,B,A it should show:
483
# and thus when truncated to D,B,A it should show
487
# because C is brought in by B in this view and D
488
# is the terminating revision id
489
# this should also preserve revision numbers: C should still be 2.1.1
490
self.assertSortAndIterate(
503
mainline_revisions=['D', 'B', 'A']
505
self.assertSortAndIterate(
513
[(0, 'A', 0, (4,), False),
514
(1, 'B', 0, (3,), False),
515
(2, 'C', 1, (2,1,1), True),
518
mainline_revisions=['D', 'B', 'A']
521
def test_mainline_revs_with_none(self):
522
# a simple test to ensure that a mainline_revs
523
# list which goes all the way to None works
524
self.assertSortAndIterate(
531
mainline_revisions=[None, 'A']
533
self.assertSortAndIterate(
537
[(0, 'A', 0, (1,), True),
540
mainline_revisions=[None, 'A']
543
def test_mainline_revs_with_ghost(self):
544
# We have a mainline, but the end of it is actually a ghost
545
# The graph that is passed to tsort has had ghosts filtered out, but
546
# the mainline history has not.
547
self.assertSortAndIterate(
551
[(0, 'C', 0, (2,), False),
552
(1, 'B', 0, (1,), True),
554
True, mainline_revisions=['A', 'B', 'C'])
556
def test_parallel_root_sequence_numbers_increase_with_merges(self):
557
"""When there are parallel roots, check their revnos."""
558
self.assertSortAndIterate(
561
'C': ['A', 'B']}.items(),
563
[(0, 'C', 0, (2,), False),
564
(1, 'B', 1, (0,1,1), True),
565
(2, 'A', 0, (1,), True),
570
def test_revnos_are_globally_assigned(self):
571
"""revnos are assigned according to the revision they derive from."""
572
# in this test we setup a number of branches that all derive from
573
# the first revision, and then merge them one at a time, which
574
# should give the revisions as they merge numbers still deriving from
575
# the revision were based on.
576
# merge 3: J: ['G', 'I']
580
# merge 2: G: ['D', 'F']
584
# merge 1: D: ['A', 'C']
589
self.assertSortAndIterate(
602
[(0, 'J', 0, (4,), False),
603
(1, 'I', 1, (1,3,2), False),
604
(2, 'H', 1, (1,3,1), True),
605
(3, 'G', 0, (3,), False),
606
(4, 'F', 1, (1,2,2), False),
607
(5, 'E', 1, (1,2,1), True),
608
(6, 'D', 0, (2,), False),
609
(7, 'C', 1, (1,1,2), False),
610
(8, 'B', 1, (1,1,1), True),
611
(9, 'A', 0, (1,), True),
616
def test_roots_and_sub_branches_versus_ghosts(self):
617
"""Extra roots and their mini branches use the same numbering.
619
All of them use the 0-node numbering.
632
self.assertSortAndIterate(
653
[( 0, 'R', 0, (6,), False),
654
( 1, 'Q', 1, (0,4,5), False),
655
( 2, 'P', 2, (0,6,1), True),
656
( 3, 'O', 1, (0,4,4), False),
657
( 4, 'N', 1, (0,4,3), False),
658
( 5, 'M', 2, (0,5,1), True),
659
( 6, 'L', 1, (0,4,2), False),
660
( 7, 'K', 1, (0,4,1), True),
661
( 8, 'J', 0, (5,), False),
662
( 9, 'I', 1, (0,3,1), True),
663
(10, 'H', 0, (4,), False),
664
(11, 'G', 1, (0,1,3), False),
665
(12, 'F', 2, (0,2,1), True),
666
(13, 'E', 1, (0,1,2), False),
667
(14, 'D', 1, (0,1,1), True),
668
(15, 'C', 0, (3,), False),
669
(16, 'B', 0, (2,), False),
670
(17, 'A', 0, (1,), True),
added
removed
bzrlib/tests/test_tsort.py
