~bzr-pqm/bzr/bzr.dev : contents of bzrlib/tests/test

~bzr-pqm/bzr/bzr.dev : (revision 1852.11.1)

# Copyright (C) 2005 by Canonical Ltd
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


"""Tests for topological sort."""


from bzrlib.tests import TestCase
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
from bzrlib.errors import GraphCycleError


class TopoSortTests(TestCase):

    def assertSortAndIterate(self, graph, result_list):
        """Check that sorting and iter_topo_order on graph works."""
        self.assertEquals(result_list, topo_sort(graph))
        self.assertEqual(result_list,
                         list(TopoSorter(graph).iter_topo_order()))

    def assertSortAndIterateRaise(self, exception_type, graph):
        """Try both iterating and topo_sorting graph and expect an exception."""
        self.assertRaises(exception_type, topo_sort, graph)
        self.assertRaises(exception_type,
                          list,
                          TopoSorter(graph).iter_topo_order())

    def test_tsort_empty(self):
        """TopoSort empty list"""
        self.assertSortAndIterate([], [])

    def test_tsort_easy(self):
        """TopoSort list with one node"""
        self.assertSortAndIterate({0: []}.items(), [0])

    def test_tsort_cycle(self):
        """TopoSort traps graph with cycles"""
        self.assertSortAndIterateRaise(GraphCycleError,
                                       {0: [1], 
                                        1: [0]}.items())

    def test_tsort_cycle_2(self):
        """TopoSort traps graph with longer cycle"""
        self.assertSortAndIterateRaise(GraphCycleError,
                                       {0: [1], 
                                        1: [2], 
                                        2: [0]}.items())
                 
    def test_tsort_1(self):
        """TopoSort simple nontrivial graph"""
        self.assertSortAndIterate({0: [3], 
                                   1: [4],
                                   2: [1, 4],
                                   3: [], 
                                   4: [0, 3]}.items(),
                                  [3, 0, 4, 1, 2])

    def test_tsort_partial(self):
        """Topological sort with partial ordering.

        If the graph does not give an order between two nodes, they are 
        returned in lexicographical order.
        """
        self.assertSortAndIterate(([(0, []),
                                   (1, [0]),
                                   (2, [0]),
                                   (3, [0]),
                                   (4, [1, 2, 3]),
                                   (5, [1, 2]),
                                   (6, [1, 2]),
                                   (7, [2, 3]),
                                   (8, [0, 1, 4, 5, 6])]),
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])


class MergeSortTests(TestCase):

    def assertSortAndIterate(self, graph, branch_tip, result_list,
            mainline_revisions=None):
        """Check that merge based sorting and iter_topo_order on graph works."""
        self.assertEquals(result_list,
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
        self.assertEqual(result_list,
            list(MergeSorter(
                graph,
                branch_tip,
                mainline_revisions=mainline_revisions).iter_topo_order()))

    def test_merge_sort_empty(self):
        # sorting of an emptygraph does not error
        self.assertSortAndIterate({}, None, [])

    def test_merge_sort_not_empty_no_tip(self):
        # merge sorting of a branch starting with None should result
        # in an empty list: no revisions are dragged in.
        self.assertSortAndIterate({0: []}.items(), None, [])

    def test_merge_sort_one_revision(self):
        # sorting with one revision as the tip returns the correct fields:
        # sequence - 0, revision id, merge depth - 0, end_of_merge
        self.assertSortAndIterate({'id': []}.items(),
                                  'id',
                                  [(0, 'id', 0, True)])
    
    def test_sequence_numbers_increase_no_merges(self):
        # emit a few revisions with no merges to check the sequence
        # numbering works in trivial cases
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['B']}.items(),
            'C',
            [(0, 'C', 0, False),
             (1, 'B', 0, False),
             (2, 'A', 0, True),
             ]
            )

    def test_sequence_numbers_increase_with_merges(self):
        # test that sequence numbers increase across merges
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['A', 'B']}.items(),
            'C',
            [(0, 'C', 0, False),
             (1, 'B', 1, True),
             (2, 'A', 0, True),
             ]
            )
        
    def test_merge_depth_with_nested_merges(self):
        # the merge depth marker should reflect the depth of the revision
        # in terms of merges out from the mainline
        # revid, depth, parents:
        #  A 0   [D, B]   
        #  B  1  [C, F]   
        #  C  1  [H] 
        #  D 0   [H, E]
        #  E  1  [G, F]
        #  F   2 [G]
        #  G  1  [H]
        #  H 0
        self.assertSortAndIterate(
            {'A': ['D', 'B'],
             'B': ['C', 'F'],
             'C': ['H'],
             'D': ['H', 'E'],
             'E': ['G', 'F'],
             'F': ['G'],
             'G': ['H'],
             'H': []
             }.items(),
            'A',
            [(0, 'A', 0, False),
             (1, 'B', 1, False),
             (2, 'C', 1, True),
             (3, 'D', 0, False),
             (4, 'E', 1, False),
             (5, 'F', 2, True),
             (6, 'G', 1, True),
             (7, 'H', 0, True),
             ]
            )
 
    def test_end_of_merge_not_last_revision_in_branch(self):
        # within a branch only the last revision gets an
        # end of merge marker.
        self.assertSortAndIterate(
            {'A': ['B'],
             'B': [],
             },
            'A',
            [(0, 'A', 0, False),
             (1, 'B', 0, True)
             ]
            )

    def test_end_of_merge_multiple_revisions_merged_at_once(self):
        # when multiple branches are merged at once, both of their
        # branch-endpoints should be listed as end-of-merge.
        # Also, the order of the multiple merges should be 
        # left-right shown top to bottom.
        # * means end of merge
        # A 0    [H, B, E] 
        # B  1   [D, C]
        # C   2  [D]       *
        # D  1   [H]       *
        # E  1   [G, F]
        # F   2  [G]       *
        # G  1   [H]       *
        # H 0    []        *
        self.assertSortAndIterate(
            {'A': ['H', 'B', 'E'],
             'B': ['D', 'C'],
             'C': ['D'],
             'D': ['H'],
             'E': ['G', 'F'],
             'F': ['G'],
             'G': ['H'],
             'H': [],
             },
            'A',
            [(0, 'A', 0, False),
             (1, 'B', 1, False),
             (2, 'C', 2, True),
             (3, 'D', 1, True),
             (4, 'E', 1, False),
             (5, 'F', 2, True),
             (6, 'G', 1, True),
             (7, 'H', 0, True),
             ]
            )

    def test_mainline_revs_partial(self):
        # when a mainline_revisions list is passed this must
        # override the graphs idea of mainline, and must also
        # truncate the output to the specified range, if needed.
        # so we test both at once: a mainline_revisions list that
        # disagrees with the graph about which revs are 'mainline'
        # and also truncates the output.
        # graph:
        # A 0 [E, B]
        # B 1 [D, C]
        # C 2 [D]
        # D 1 [E]
        # E 0
        # with a mainline of NONE,E,A (the inferred one) this will show the merge
        # depths above.
        # with a overriden mainline of NONE,E,D,B,A it should show:
        # A 0
        # B 0
        # C 1
        # D 0
        # E 0
        # and thus when truncated to D,B,A it should show
        # A 0
        # B 0
        # C 1 
        # because C is brought in by B in this view and D
        # is the terminating revision id
        self.assertSortAndIterate(
            {'A': ['E', 'B'],
             'B': ['D', 'C'],
             'C': ['D'],
             'D': ['E'],
             'E': []
             },
            'A',
            [(0, 'A', 0, False),
             (1, 'B', 0, False),
             (2, 'C', 1, True),
             ],
            mainline_revisions=['D', 'B', 'A']
            )

    def test_mainline_revs_with_none(self):
        # a simple test to ensure that a mainline_revs
        # list which goes all the way to None works
        self.assertSortAndIterate(
            {'A': [],
             },
            'A',
            [(0, 'A', 0, True),
             ],
            mainline_revisions=[None, 'A']
            )


1185.16.113 by mbp at sourcefrog Add topo_sort utility function	1	# Copyright (C) 2005 by Canonical Ltd
	2	#
	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.
	7	#
	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.
	12	#
	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
	16
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	17
1570.1.6 by Robert Collins Update fast topological_sort to be a function and to have the topo_sort tests run against it.	18	"""Tests for topological sort."""
	19
	20
1185.31.25 by John Arbash Meinel Renamed all of the tests from selftest/foo.py to tests/test_foo.py	21	from bzrlib.tests import TestCase
1624.1.2 by Robert Collins Add MergeSort facility to bzrlib.tsort.	22	from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
1185.16.114 by mbp at sourcefrog Improved topological sort	23	from bzrlib.errors import GraphCycleError
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	24
1570.1.6 by Robert Collins Update fast topological_sort to be a function and to have the topo_sort tests run against it.	25
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	26	class TopoSortTests(TestCase):
	27
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	28	def assertSortAndIterate(self, graph, result_list):
	29	"""Check that sorting and iter_topo_order on graph works."""
	30	self.assertEquals(result_list, topo_sort(graph))
	31	self.assertEqual(result_list,
	32	list(TopoSorter(graph).iter_topo_order()))
	33
	34	def assertSortAndIterateRaise(self, exception_type, graph):
	35	"""Try both iterating and topo_sorting graph and expect an exception."""
	36	self.assertRaises(exception_type, topo_sort, graph)
	37	self.assertRaises(exception_type,
	38	list,
	39	TopoSorter(graph).iter_topo_order())
	40
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	41	def test_tsort_empty(self):
	42	"""TopoSort empty list"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	43	self.assertSortAndIterate([], [])
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	44
	45	def test_tsort_easy(self):
1185.16.114 by mbp at sourcefrog Improved topological sort	46	"""TopoSort list with one node"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	47	self.assertSortAndIterate({0: []}.items(), [0])
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	48
	49	def test_tsort_cycle(self):
1185.16.114 by mbp at sourcefrog Improved topological sort	50	"""TopoSort traps graph with cycles"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	51	self.assertSortAndIterateRaise(GraphCycleError,
	52	{0: [1],
	53	1: [0]}.items())
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	54
1185.16.114 by mbp at sourcefrog Improved topological sort	55	def test_tsort_cycle_2(self):
1185.16.114 by mbp at sourcefrog Improved topological sort	56	"""TopoSort traps graph with longer cycle"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	57	self.assertSortAndIterateRaise(GraphCycleError,
	58	{0: [1],
	59	1: [2],
	60	2: [0]}.items())
1185.16.114 by mbp at sourcefrog Improved topological sort	61
1185.16.113 by mbp at sourcefrog Add topo_sort utility function	62	def test_tsort_1(self):
	63	"""TopoSort simple nontrivial graph"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	64	self.assertSortAndIterate({0: [3],
	65	1: [4],
	66	2: [1, 4],
	67	3: [],
	68	4: [0, 3]}.items(),
	69	[3, 0, 4, 1, 2])
1185.16.115 by mbp at sourcefrog Another topo_sort test	70
	71	def test_tsort_partial(self):
	72	"""Topological sort with partial ordering.
	73
	74	If the graph does not give an order between two nodes, they are
	75	returned in lexicographical order.
	76	"""
1570.1.7 by Robert Collins Replace the slow topo_sort routine with a much faster one for non trivial datasets.	77	self.assertSortAndIterate(([(0, []),
	78	(1, [0]),
	79	(2, [0]),
	80	(3, [0]),
	81	(4, [1, 2, 3]),
	82	(5, [1, 2]),
	83	(6, [1, 2]),
	84	(7, [2, 3]),
	85	(8, [0, 1, 4, 5, 6])]),
	86	[0, 1, 2, 3, 4, 5, 6, 7, 8])
1624.1.2 by Robert Collins Add MergeSort facility to bzrlib.tsort.	87
	88
	89	class MergeSortTests(TestCase):
	90
1624.1.3 by Robert Collins Convert log to use the new tsort.merge_sort routine.	91	def assertSortAndIterate(self, graph, branch_tip, result_list,
	92	mainline_revisions=None):
1624.1.2 by Robert Collins Add MergeSort facility to bzrlib.tsort.	93	"""Check that merge based sorting and iter_topo_order on graph works."""
1624.1.3 by Robert Collins Convert log to use the new tsort.merge_sort routine.	94	self.assertEquals(result_list,
	95	merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
1624.1.2 by Robert Collins Add MergeSort facility to bzrlib.tsort.	96	self.assertEqual(result_list,
1624.1.3 by Robert Collins Convert log to use the new tsort.merge_sort routine.	97	list(MergeSorter(
	98	graph,
	99	branch_tip,
	100	mainline_revisions=mainline_revisions).iter_topo_order()))
1624.1.2 by Robert Collins Add MergeSort facility to bzrlib.tsort.	101
	102	def test_merge_sort_empty(self):
	103	# sorting of an emptygraph does not error
	104	self.assertSortAndIterate({}, None, [])
	105
	106	def test_merge_sort_not_empty_no_tip(self):
	107	# merge sorting of a branch starting with None should result
	108	# in an empty list: no revisions are dragged in.
	109	self.assertSortAndIterate({0: []}.items(), None, [])
	110
	111	def test_merge_sort_one_revision(self):
	112	# sorting with one revision as the tip returns the correct fields:
	113	# sequence - 0, revision id, merge depth - 0, end_of_merge
	114	self.assertSortAndIterate({'id': []}.items(),
	115	'id',
	116	[(0, 'id', 0, True)])
	117
	118	def test_sequence_numbers_increase_no_merges(self):
	119	# emit a few revisions with no merges to check the sequence
	120	# numbering works in trivial cases
	121	self.assertSortAndIterate(
	122	{'A': [],
	123	'B': ['A'],
	124	'C': ['B']}.items(),
	125	'C',
	126	[(0, 'C', 0, False),
	127	(1, 'B', 0, False),
	128	(2, 'A', 0, True),
	129	]
	130	)
	131
	132	def test_sequence_numbers_increase_with_merges(self):
	133	# test that sequence numbers increase across merges
	134	self.assertSortAndIterate(
	135	{'A': [],
	136	'B': ['A'],
	137	'C': ['A', 'B']}.items(),
	138	'C',
	139	[(0, 'C', 0, False),
	140	(1, 'B', 1, True),
	141	(2, 'A', 0, True),
	142	]
	143	)
	144
	145	def test_merge_depth_with_nested_merges(self):
	146	# the merge depth marker should reflect the depth of the revision
	147	# in terms of merges out from the mainline
	148	# revid, depth, parents:
	149	# A 0 [D, B]
	150	# B 1 [C, F]
	151	# C 1 [H]
	152	# D 0 [H, E]
	153	# E 1 [G, F]
	154	# F 2 [G]
	155	# G 1 [H]
	156	# H 0
	157	self.assertSortAndIterate(
	158	{'A': ['D', 'B'],
	159	'B': ['C', 'F'],
	160	'C': ['H'],
	161	'D': ['H', 'E'],
	162	'E': ['G', 'F'],
	163	'F': ['G'],
	164	'G': ['H'],
165	'H': []
166	}.items(),
167	'A',
168	[(0, 'A', 0, False),
169	(1, 'B', 1, False),
170	(2, 'C', 1, True),
171	(3, 'D', 0, False),
172	(4, 'E', 1, False),
173	(5, 'F', 2, True),
174	(6, 'G', 1, True),
175	(7, 'H', 0, True),
176	]
177	)
178
179	def test_end_of_merge_not_last_revision_in_branch(self):
180	# within a branch only the last revision gets an
181	# end of merge marker.
182	self.assertSortAndIterate(
183	{'A': ['B'],
184	'B': [],
185	},
186	'A',
187	[(0, 'A', 0, False),
188	(1, 'B', 0, True)
189	]
190	)
191
192	def test_end_of_merge_multiple_revisions_merged_at_once(self):
193	# when multiple branches are merged at once, both of their
194	# branch-endpoints should be listed as end-of-merge.
195	# Also, the order of the multiple merges should be
196	# left-right shown top to bottom.
197	# * means end of merge
198	# A 0 [H, B, E]
199	# B 1 [D, C]
200	# C 2 [D] *
201	# D 1 [H] *
202	# E 1 [G, F]
203	# F 2 [G] *
204	# G 1 [H] *
205	# H 0 [] *
206	self.assertSortAndIterate(
207	{'A': ['H', 'B', 'E'],
208	'B': ['D', 'C'],
209	'C': ['D'],
210	'D': ['H'],
211	'E': ['G', 'F'],
212	'F': ['G'],
213	'G': ['H'],
214	'H': [],
215	},
216	'A',
217	[(0, 'A', 0, False),
218	(1, 'B', 1, False),
219	(2, 'C', 2, True),
220	(3, 'D', 1, True),
221	(4, 'E', 1, False),
222	(5, 'F', 2, True),
223	(6, 'G', 1, True),
224	(7, 'H', 0, True),
225	]
226	)
1624.1.3 by Robert Collins Convert log to use the new tsort.merge_sort routine.	227
	228	def test_mainline_revs_partial(self):
	229	# when a mainline_revisions list is passed this must
	230	# override the graphs idea of mainline, and must also
	231	# truncate the output to the specified range, if needed.
	232	# so we test both at once: a mainline_revisions list that
	233	# disagrees with the graph about which revs are 'mainline'
	234	# and also truncates the output.
	235	# graph:
	236	# A 0 [E, B]
	237	# B 1 [D, C]
	238	# C 2 [D]
	239	# D 1 [E]
	240	# E 0
	241	# with a mainline of NONE,E,A (the inferred one) this will show the merge
	242	# depths above.
	243	# with a overriden mainline of NONE,E,D,B,A it should show:
	244	# A 0
	245	# B 0
	246	# C 1
	247	# D 0
	248	# E 0
	249	# and thus when truncated to D,B,A it should show
	250	# A 0
	251	# B 0
	252	# C 1
	253	# because C is brought in by B in this view and D
	254	# is the terminating revision id
	255	self.assertSortAndIterate(
	256	{'A': ['E', 'B'],
	257	'B': ['D', 'C'],
	258	'C': ['D'],
	259	'D': ['E'],
	260	'E': []
	261	},
	262	'A',
	263	[(0, 'A', 0, False),
	264	(1, 'B', 0, False),
	265	(2, 'C', 1, True),
	266	],
	267	mainline_revisions=['D', 'B', 'A']
	268	)
	269
	270	def test_mainline_revs_with_none(self):
	271	# a simple test to ensure that a mainline_revs
	272	# list which goes all the way to None works
	273	self.assertSortAndIterate(
	274	{'A': [],
	275	},
	276	'A',
	277	[(0, 'A', 0, True),
	278	],
	279	mainline_revisions=[None, 'A']
	280	)
	281