path: root/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
            )