test_tsort.py :  » Development » Bazaar » bzr-2.2b3 » bzrlib » tests » Python Open Source

Home
Python Open Source
1.3.1.2 Python
2.Ajax
3.Aspect Oriented
4.Blog
5.Build
6.Business Application
7.Chart Report
8.Content Management Systems
9.Cryptographic
10.Database
11.Development
12.Editor
13.Email
14.ERP
15.Game 2D 3D
16.GIS
17.GUI
18.IDE
19.Installer
20.IRC
21.Issue Tracker
22.Language Interface
23.Log
24.Math
25.Media Sound Audio
26.Mobile
27.Network
28.Parser
29.PDF
30.Project Management
31.RSS
32.Search
33.Security
34.Template Engines
35.Test
36.UML
37.USB Serial
38.Web Frameworks
39.Web Server
40.Web Services
41.Web Unit
42.Wiki
43.Windows
44.XML
Python Open Source » Development » Bazaar 
Bazaar » bzr 2.2b3 » bzrlib » tests » test_tsort.py
# Copyright (C) 2005 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA


"""Tests for topological sort."""

import pprint

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


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 assertSortAndIterateOrder(self, graph):
        """Check topo_sort and iter_topo_order is genuinely topological order.

        For every child in the graph, check if it comes after all of it's
        parents.
        """
        sort_result = topo_sort(graph)
        iter_result = list(TopoSorter(graph).iter_topo_order())
        for (node, parents) in graph:
            for parent in parents:
                if sort_result.index(node) < sort_result.index(parent):
                    self.fail("parent %s must come before child %s:\n%s"
                              % (parent, node, sort_result))
                if iter_result.index(node) < iter_result.index(parent):
                    self.fail("parent %s must come before child %s:\n%s"
                              % (parent, node, iter_result))

    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_topo_sort_cycle_with_tail(self):
        """TopoSort traps graph with longer cycle"""
        self.assertSortAndIterateRaise(GraphCycleError,
                                       {0: [1],
                                        1: [2],
                                        2: [3, 4],
                                        3: [0],
                                        4: []}.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.

        Multiple correct orderings are possible, so test for 
        correctness, not for exact match on the resulting list.
        """
        self.assertSortAndIterateOrder([(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])])

    def test_tsort_unincluded_parent(self):
        """Sort nodes, but don't include some parents in the output"""
        self.assertSortAndIterate([(0, [1]),
                                   (1, [2])],
                                   [1, 0])


class MergeSortTests(TestCase):

    def assertSortAndIterate(self, graph, branch_tip, result_list,
            generate_revno, mainline_revisions=None):
        """Check that merge based sorting and iter_topo_order on graph works."""
        value = merge_sort(graph, branch_tip,
                           mainline_revisions=mainline_revisions,
                           generate_revno=generate_revno)
        if result_list != value:
            self.assertEqualDiff(pprint.pformat(result_list),
                                 pprint.pformat(value))
        self.assertEqual(result_list,
            list(MergeSorter(
                graph,
                branch_tip,
                mainline_revisions=mainline_revisions,
                generate_revno=generate_revno,
                ).iter_topo_order()))

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

    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, [], False)
        self.assertSortAndIterate({0: []}.items(), None, [], True)

    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)],
                                  False)
        self.assertSortAndIterate({'id': []}.items(),
                                  'id',
                                  [(0, 'id', 0, (1,), True)],
                                  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),
             ],
            False
            )
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['B']}.items(),
            'C',
            [(0, 'C', 0, (3,), False),
             (1, 'B', 0, (2,), False),
             (2, 'A', 0, (1,), True),
             ],
            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),
             ],
            False
            )
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['A', 'B']}.items(),
            'C',
            [(0, 'C', 0, (2,), False),
             (1, 'B', 1, (1,1,1), True),
             (2, 'A', 0, (1,), True),
             ],
            True
            )

    def test_merge_sort_race(self):
        # A
        # |
        # B-.
        # |\ \
        # | | C
        # | |/
        # | D
        # |/
        # F
        graph = {'A': [],
                 'B': ['A'],
                 'C': ['B'],
                 'D': ['B', 'C'],
                 'F': ['B', 'D'],
                 }
        self.assertSortAndIterate(graph, 'F',
            [(0, 'F', 0, (3,), False),
             (1, 'D', 1, (2,2,1), False),
             (2, 'C', 2, (2,1,1), True),
             (3, 'B', 0, (2,), False),
             (4, 'A', 0, (1,), True),
             ], True)
        # A
        # |
        # B-.
        # |\ \
        # | X C
        # | |/
        # | D
        # |/
        # F
        graph = {'A': [],
                 'B': ['A'],
                 'C': ['B'],
                 'X': ['B'],
                 'D': ['X', 'C'],
                 'F': ['B', 'D'],
                 }
        self.assertSortAndIterate(graph, 'F',
            [(0, 'F', 0, (3,), False),
             (1, 'D', 1, (2,1,2), False),
             (2, 'C', 2, (2,2,1), True),
             (3, 'X', 1, (2,1,1), True),
             (4, 'B', 0, (2,), False),
             (5, 'A', 0, (1,), True),
             ], 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),
             ],
            False
            )
        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, (3,),  False),
             (1, 'B', 1, (1,3,2), False),
             (2, 'C', 1, (1,3,1), True),
             (3, 'D', 0, (2,), False),
             (4, 'E', 1, (1,1,2), False),
             (5, 'F', 2, (1,2,1), True),
             (6, 'G', 1, (1,1,1), True),
             (7, 'H', 0, (1,), True),
             ],
            True
            )

    def test_dotted_revnos_with_simple_merges(self):
        # A         1
        # |\
        # B C       2, 1.1.1
        # | |\
        # D E F     3, 1.1.2, 1.2.1
        # |/ /|
        # G H I     4, 1.2.2, 1.3.1
        # |/ /
        # J K       5, 1.3.2
        # |/
        # L         6
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['A'],
             'D': ['B'],
             'E': ['C'],
             'F': ['C'],
             'G': ['D', 'E'],
             'H': ['F'],
             'I': ['F'],
             'J': ['G', 'H'],
             'K': ['I'],
             'L': ['J', 'K'],
            }.items(),
            'L',
            [(0, 'L', 0, (6,), False),
             (1, 'K', 1, (1,3,2), False),
             (2, 'I', 1, (1,3,1), True),
             (3, 'J', 0, (5,), False),
             (4, 'H', 1, (1,2,2), False),
             (5, 'F', 1, (1,2,1), True),
             (6, 'G', 0, (4,), False),
             (7, 'E', 1, (1,1,2), False),
             (8, 'C', 1, (1,1,1), True),
             (9, 'D', 0, (3,), False),
             (10, 'B', 0, (2,), False),
             (11, 'A', 0, (1,),  True),
             ],
            True
            )
        # Adding a shortcut from the first revision should not change any of
        # the existing numbers
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['A'],
             'D': ['B'],
             'E': ['C'],
             'F': ['C'],
             'G': ['D', 'E'],
             'H': ['F'],
             'I': ['F'],
             'J': ['G', 'H'],
             'K': ['I'],
             'L': ['J', 'K'],
             'M': ['A'],
             'N': ['L', 'M'],
            }.items(),
            'N',
            [(0, 'N', 0, (7,), False),
             (1, 'M', 1, (1,4,1), True),
             (2, 'L', 0, (6,), False),
             (3, 'K', 1, (1,3,2), False),
             (4, 'I', 1, (1,3,1), True),
             (5, 'J', 0, (5,), False),
             (6, 'H', 1, (1,2,2), False),
             (7, 'F', 1, (1,2,1), True),
             (8, 'G', 0, (4,), False),
             (9, 'E', 1, (1,1,2), False),
             (10, 'C', 1, (1,1,1), True),
             (11, 'D', 0, (3,), False),
             (12, 'B', 0, (2,), False),
             (13, 'A', 0, (1,),  True),
             ],
            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)
             ],
            False
            )
        self.assertSortAndIterate(
            {'A': ['B'],
             'B': [],
             },
            'A',
            [(0, 'A', 0, (2,), False),
             (1, 'B', 0, (1,), True)
             ],
            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),
             ],
            False
            )
        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, (2,), False),
             (1, 'B', 1, (1,3,2), False),
             (2, 'C', 2, (1,4,1), True),
             (3, 'D', 1, (1,3,1), True),
             (4, 'E', 1, (1,1,2), False),
             (5, 'F', 2, (1,2,1), True),
             (6, 'G', 1, (1,1,1), True),
             (7, 'H', 0, (1,), True),
             ],
            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
        # this should also preserve revision numbers: C should still be 2.1.1
        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),
             ],
            False,
            mainline_revisions=['D', 'B', 'A']
            )
        self.assertSortAndIterate(
            {'A': ['E', 'B'],
             'B': ['D', 'C'],
             'C': ['D'],
             'D': ['E'],
             'E': []
             },
            'A',
            [(0, 'A', 0, (4,), False),
             (1, 'B', 0, (3,), False),
             (2, 'C', 1, (2,1,1), True),
             ],
            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),
             ],
            False,
            mainline_revisions=[None, 'A']
            )
        self.assertSortAndIterate(
            {'A': [],
             },
            'A',
            [(0, 'A', 0, (1,), True),
             ],
            True,
            mainline_revisions=[None, 'A']
            )

    def test_mainline_revs_with_ghost(self):
        # We have a mainline, but the end of it is actually a ghost
        # The graph that is passed to tsort has had ghosts filtered out, but
        # the mainline history has not.
        self.assertSortAndIterate(
            {'B':[],
             'C':['B']}.items(),
            'C',
            [(0, 'C', 0, (2,), False),
             (1, 'B', 0, (1,), True),
             ],
             True, mainline_revisions=['A', 'B', 'C'])

    def test_parallel_root_sequence_numbers_increase_with_merges(self):
        """When there are parallel roots, check their revnos."""
        self.assertSortAndIterate(
            {'A': [],
             'B': [],
             'C': ['A', 'B']}.items(),
            'C',
            [(0, 'C', 0, (2,), False),
             (1, 'B', 1, (0,1,1), True),
             (2, 'A', 0, (1,), True),
             ],
            True
            )

    def test_revnos_are_globally_assigned(self):
        """revnos are assigned according to the revision they derive from."""
        # in this test we setup a number of branches that all derive from
        # the first revision, and then merge them one at a time, which
        # should give the revisions as they merge numbers still deriving from
        # the revision were based on.
        # merge 3: J: ['G', 'I']
        # branch 3:
        #  I: ['H']
        #  H: ['A']
        # merge 2: G: ['D', 'F']
        # branch 2:
        #  F: ['E']
        #  E: ['A']
        # merge 1: D: ['A', 'C']
        # branch 1:
        #  C: ['B']
        #  B: ['A']
        # root: A: []
        self.assertSortAndIterate(
            {'J': ['G', 'I'],
             'I': ['H',],
             'H': ['A'],
             'G': ['D', 'F'],
             'F': ['E'],
             'E': ['A'],
             'D': ['A', 'C'],
             'C': ['B'],
             'B': ['A'],
             'A': [],
             }.items(),
            'J',
            [(0, 'J', 0, (4,), False),
             (1, 'I', 1, (1,3,2), False),
             (2, 'H', 1, (1,3,1), True),
             (3, 'G', 0, (3,), False),
             (4, 'F', 1, (1,2,2), False),
             (5, 'E', 1, (1,2,1), True),
             (6, 'D', 0, (2,), False),
             (7, 'C', 1, (1,1,2), False),
             (8, 'B', 1, (1,1,1), True),
             (9, 'A', 0, (1,), True),
             ],
            True
            )

    def test_roots_and_sub_branches_versus_ghosts(self):
        """Extra roots and their mini branches use the same numbering.

        All of them use the 0-node numbering.
        """
        #       A D   K
        #       | |\  |\
        #       B E F L M
        #       | |/  |/
        #       C G   N
        #       |/    |\
        #       H I   O P
        #       |/    |/
        #       J     Q
        #       |.---'
        #       R
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['B'],
             'D': [],
             'E': ['D'],
             'F': ['D'],
             'G': ['E', 'F'],
             'H': ['C', 'G'],
             'I': [],
             'J': ['H', 'I'],
             'K': [],
             'L': ['K'],
             'M': ['K'],
             'N': ['L', 'M'],
             'O': ['N'],
             'P': ['N'],
             'Q': ['O', 'P'],
             'R': ['J', 'Q'],
            }.items(),
            'R',
            [( 0, 'R', 0, (6,), False),
             ( 1, 'Q', 1, (0,4,5), False),
             ( 2, 'P', 2, (0,6,1), True),
             ( 3, 'O', 1, (0,4,4), False),
             ( 4, 'N', 1, (0,4,3), False),
             ( 5, 'M', 2, (0,5,1), True),
             ( 6, 'L', 1, (0,4,2), False),
             ( 7, 'K', 1, (0,4,1), True),
             ( 8, 'J', 0, (5,), False),
             ( 9, 'I', 1, (0,3,1), True),
             (10, 'H', 0, (4,), False),
             (11, 'G', 1, (0,1,3), False),
             (12, 'F', 2, (0,2,1), True),
             (13, 'E', 1, (0,1,2), False),
             (14, 'D', 1, (0,1,1), True),
             (15, 'C', 0, (3,), False),
             (16, 'B', 0, (2,), False),
             (17, 'A', 0, (1,), True),
             ],
            True
            )
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.