path: root/bzrlib/tests/test__known_graph.py

# Copyright (C) 2009, 2010, 2011 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 the python and pyrex extensions of KnownGraph"""

import pprint

from bzrlib import (
    errors,
    _known_graph_py,
    tests,
    )
from bzrlib.tests import test_graph
from bzrlib.revision import NULL_REVISION
from bzrlib.tests.scenarios import load_tests_apply_scenarios
from bzrlib.tests import (
    features,
    )


def caching_scenarios():
    scenarios = [
        ('python', {'module': _known_graph_py, 'do_cache': True}),
    ]
    if compiled_known_graph_feature.available():
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
                                'do_cache': True}))
    return scenarios


def non_caching_scenarios():
    scenarios = [
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
    ]
    if compiled_known_graph_feature.available():
        scenarios.append(
            ('C-nocache', {'module': compiled_known_graph_feature.module,
                           'do_cache': False}))
    return scenarios


load_tests = load_tests_apply_scenarios


compiled_known_graph_feature = features.ModuleAvailableFeature(
    'bzrlib._known_graph_pyx')


#  a
#  |\
#  b |
#  | |
#  c |
#   \|
#    d
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}


class TestCaseWithKnownGraph(tests.TestCase):

    scenarios = caching_scenarios()
    module = None # Set by load_tests

    def make_known_graph(self, ancestry):
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)


class TestKnownGraph(TestCaseWithKnownGraph):

    def assertGDFO(self, graph, rev, gdfo):
        node = graph._nodes[rev]
        self.assertEqual(gdfo, node.gdfo)

    def test_children_ancestry1(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
        self.assertEqual(['rev2a', 'rev2b'],
                         sorted(graph.get_child_keys('rev1')))
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')

    def test_parent_ancestry1(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
        self.assertEqual(['rev2b', 'rev3'],
                         sorted(graph.get_parent_keys('rev4')))
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
    
    def test_parent_with_ghost(self):
        graph = self.make_known_graph(test_graph.with_ghost)
        self.assertEqual(None, graph.get_parent_keys('g'))

    def test_gdfo_ancestry_1(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertGDFO(graph, 'rev1', 2)
        self.assertGDFO(graph, 'rev2b', 3)
        self.assertGDFO(graph, 'rev2a', 3)
        self.assertGDFO(graph, 'rev3', 4)
        self.assertGDFO(graph, 'rev4', 5)

    def test_gdfo_feature_branch(self):
        graph = self.make_known_graph(test_graph.feature_branch)
        self.assertGDFO(graph, 'rev1', 2)
        self.assertGDFO(graph, 'rev2b', 3)
        self.assertGDFO(graph, 'rev3b', 4)

    def test_gdfo_extended_history_shortcut(self):
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
        self.assertGDFO(graph, 'a', 2)
        self.assertGDFO(graph, 'b', 3)
        self.assertGDFO(graph, 'c', 4)
        self.assertGDFO(graph, 'd', 5)
        self.assertGDFO(graph, 'e', 6)
        self.assertGDFO(graph, 'f', 6)

    def test_gdfo_with_ghost(self):
        graph = self.make_known_graph(test_graph.with_ghost)
        self.assertGDFO(graph, 'f', 2)
        self.assertGDFO(graph, 'e', 3)
        self.assertGDFO(graph, 'g', 1)
        self.assertGDFO(graph, 'b', 4)
        self.assertGDFO(graph, 'd', 4)
        self.assertGDFO(graph, 'a', 5)
        self.assertGDFO(graph, 'c', 5)

    def test_add_existing_node(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        # Add a node that already exists with identical content
        # This is a 'no-op'
        self.assertGDFO(graph, 'rev4', 5)
        graph.add_node('rev4', ['rev3', 'rev2b'])
        self.assertGDFO(graph, 'rev4', 5)
        # This also works if we use a tuple rather than a list
        graph.add_node('rev4', ('rev3', 'rev2b'))

    def test_add_existing_node_mismatched_parents(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertRaises(ValueError, graph.add_node, 'rev4',
                          ['rev2b', 'rev3'])

    def test_add_node_with_ghost_parent(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        graph.add_node('rev5', ['rev2b', 'revGhost'])
        self.assertGDFO(graph, 'rev5', 4)
        self.assertGDFO(graph, 'revGhost', 1)

    def test_add_new_root(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        graph.add_node('rev5', [])
        self.assertGDFO(graph, 'rev5', 1)

    def test_add_with_all_ghost_parents(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        graph.add_node('rev5', ['ghost'])
        self.assertGDFO(graph, 'rev5', 2)
        self.assertGDFO(graph, 'ghost', 1)

    def test_gdfo_after_add_node(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual([], graph.get_child_keys('rev4'))
        graph.add_node('rev5', ['rev4'])
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
        self.assertEqual([], graph.get_child_keys('rev5'))
        self.assertGDFO(graph, 'rev5', 6)
        graph.add_node('rev6', ['rev2b'])
        graph.add_node('rev7', ['rev6'])
        graph.add_node('rev8', ['rev7', 'rev5'])
        self.assertGDFO(graph, 'rev5', 6)
        self.assertGDFO(graph, 'rev6', 4)
        self.assertGDFO(graph, 'rev7', 5)
        self.assertGDFO(graph, 'rev8', 7)

    def test_fill_in_ghost(self):
        graph = self.make_known_graph(test_graph.with_ghost)
        # Add in a couple nodes and then fill in the 'ghost' so that it should
        # cause renumbering of children nodes
        graph.add_node('x', [])
        graph.add_node('y', ['x'])
        graph.add_node('z', ['y'])
        graph.add_node('g', ['z'])
        self.assertGDFO(graph, 'f', 2)
        self.assertGDFO(graph, 'e', 3)
        self.assertGDFO(graph, 'x', 1)
        self.assertGDFO(graph, 'y', 2)
        self.assertGDFO(graph, 'z', 3)
        self.assertGDFO(graph, 'g', 4)
        self.assertGDFO(graph, 'b', 4)
        self.assertGDFO(graph, 'd', 5)
        self.assertGDFO(graph, 'a', 5)
        self.assertGDFO(graph, 'c', 6)


class TestKnownGraphHeads(TestCaseWithKnownGraph):

    scenarios = caching_scenarios() + non_caching_scenarios()
    do_cache = None # Set by load_tests

    def test_heads_null(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual(set(['null:']), graph.heads(['null:']))
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))

    def test_heads_one(self):
        # A single node will always be a head
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual(set(['null:']), graph.heads(['null:']))
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))

    def test_heads_single(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))

    def test_heads_two_heads(self):
        graph = self.make_known_graph(test_graph.ancestry_1)
        self.assertEqual(set(['rev2a', 'rev2b']),
                         graph.heads(['rev2a', 'rev2b']))
        self.assertEqual(set(['rev3', 'rev2b']),
                         graph.heads(['rev3', 'rev2b']))

    def test_heads_criss_cross(self):
        graph = self.make_known_graph(test_graph.criss_cross)
        self.assertEqual(set(['rev2a']),
                         graph.heads(['rev2a', 'rev1']))
        self.assertEqual(set(['rev2b']),
                         graph.heads(['rev2b', 'rev1']))
        self.assertEqual(set(['rev3a']),
                         graph.heads(['rev3a', 'rev1']))
        self.assertEqual(set(['rev3b']),
                         graph.heads(['rev3b', 'rev1']))
        self.assertEqual(set(['rev2a', 'rev2b']),
                         graph.heads(['rev2a', 'rev2b']))
        self.assertEqual(set(['rev3a']),
                         graph.heads(['rev3a', 'rev2a']))
        self.assertEqual(set(['rev3a']),
                         graph.heads(['rev3a', 'rev2b']))
        self.assertEqual(set(['rev3a']),
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
        self.assertEqual(set(['rev3b']),
                         graph.heads(['rev3b', 'rev2a']))
        self.assertEqual(set(['rev3b']),
                         graph.heads(['rev3b', 'rev2b']))
        self.assertEqual(set(['rev3b']),
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
        self.assertEqual(set(['rev3a', 'rev3b']),
                         graph.heads(['rev3a', 'rev3b']))
        self.assertEqual(set(['rev3a', 'rev3b']),
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))

    def test_heads_shortcut(self):
        graph = self.make_known_graph(test_graph.history_shortcut)
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
        self.assertEqual(set(['rev3a', 'rev3b']),
                         graph.heads(['rev3a', 'rev3b']))
        self.assertEqual(set(['rev3a', 'rev3b']),
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
        self.assertEqual(set(['rev2a', 'rev3b']),
                         graph.heads(['rev2a', 'rev3b']))
        self.assertEqual(set(['rev2c', 'rev3a']),
                         graph.heads(['rev2c', 'rev3a']))

    def test_heads_linear(self):
        graph = self.make_known_graph(test_graph.racing_shortcuts)
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))

    def test_heads_alt_merge(self):
        graph = self.make_known_graph(alt_merge)
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))

    def test_heads_with_ghost(self):
        graph = self.make_known_graph(test_graph.with_ghost)
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))

    def test_filling_in_ghosts_resets_head_cache(self):
        graph = self.make_known_graph(test_graph.with_ghost)
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
        # 'g' is filled in, and decends from 'e', so the heads result is now
        # different
        graph.add_node('g', ['e'])
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))


class TestKnownGraphTopoSort(TestCaseWithKnownGraph):

    def assertTopoSortOrder(self, ancestry):
        """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.
        """
        graph = self.make_known_graph(ancestry)
        sort_result = graph.topo_sort()
        # We should have an entry in sort_result for every entry present in the
        # graph.
        self.assertEqual(len(ancestry), len(sort_result))
        node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
        for node in sort_result:
            parents = ancestry[node]
            for parent in parents:
                if parent not in ancestry:
                    # ghost
                    continue
                if node_idx[node] <= node_idx[parent]:
                    self.fail("parent %s must come before child %s:\n%s"
                              % (parent, node, sort_result))

    def test_topo_sort_empty(self):
        """TopoSort empty list"""
        self.assertTopoSortOrder({})

    def test_topo_sort_easy(self):
        """TopoSort list with one node"""
        self.assertTopoSortOrder({0: []})

    def test_topo_sort_cycle(self):
        """TopoSort traps graph with cycles"""
        g = self.make_known_graph({0: [1],
                                  1: [0]})
        self.assertRaises(errors.GraphCycleError, g.topo_sort)

    def test_topo_sort_cycle_2(self):
        """TopoSort traps graph with longer cycle"""
        g = self.make_known_graph({0: [1],
                                   1: [2],
                                   2: [0]})
        self.assertRaises(errors.GraphCycleError, g.topo_sort)

    def test_topo_sort_cycle_with_tail(self):
        """TopoSort traps graph with longer cycle"""
        g = self.make_known_graph({0: [1],
                                   1: [2],
                                   2: [3, 4],
                                   3: [0],
                                   4: []})
        self.assertRaises(errors.GraphCycleError, g.topo_sort)

    def test_topo_sort_1(self):
        """TopoSort simple nontrivial graph"""
        self.assertTopoSortOrder({0: [3],
                                  1: [4],
                                  2: [1, 4],
                                  3: [],
                                  4: [0, 3]})

    def test_topo_sort_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.assertTopoSortOrder({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_topo_sort_ghost_parent(self):
        """Sort nodes, but don't include some parents in the output"""
        self.assertTopoSortOrder({0: [1],
                                  1: [2]})


class TestKnownGraphMergeSort(TestCaseWithKnownGraph):

    def assertSortAndIterate(self, ancestry, branch_tip, result_list):
        """Check that merge based sorting and iter_topo_order on graph works."""
        graph = self.make_known_graph(ancestry)
        value = graph.merge_sort(branch_tip)
        value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
                 for n in value]
        if result_list != value:
            self.assertEqualDiff(pprint.pformat(result_list),
                                 pprint.pformat(value))

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

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

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

    def test_sequence_numbers_increase_with_merges(self):
        # test that sequence numbers increase across merges
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['A', 'B']},
            'C',
            [('C', 0, (2,), False),
             ('B', 1, (1,1,1), True),
             ('A', 0, (1,), 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',
            [('F', 0, (3,), False),
             ('D', 1, (2,2,1), False),
             ('C', 2, (2,1,1), True),
             ('B', 0, (2,), False),
             ('A', 0, (1,), 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',
            [('F', 0, (3,), False),
             ('D', 1, (2,1,2), False),
             ('C', 2, (2,2,1), True),
             ('X', 1, (2,1,1), True),
             ('B', 0, (2,), False),
             ('A', 0, (1,), 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': []
             },
            'A',
            [('A', 0, (3,),  False),
             ('B', 1, (1,3,2), False),
             ('C', 1, (1,3,1), True),
             ('D', 0, (2,), False),
             ('E', 1, (1,1,2), False),
             ('F', 2, (1,2,1), True),
             ('G', 1, (1,1,1), True),
             ('H', 0, (1,), 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'],
            },
            'L',
            [('L', 0, (6,), False),
             ('K', 1, (1,3,2), False),
             ('I', 1, (1,3,1), True),
             ('J', 0, (5,), False),
             ('H', 1, (1,2,2), False),
             ('F', 1, (1,2,1), True),
             ('G', 0, (4,), False),
             ('E', 1, (1,1,2), False),
             ('C', 1, (1,1,1), True),
             ('D', 0, (3,), False),
             ('B', 0, (2,), False),
             ('A', 0, (1,),  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'],
            },
            'N',
            [('N', 0, (7,), False),
             ('M', 1, (1,4,1), True),
             ('L', 0, (6,), False),
             ('K', 1, (1,3,2), False),
             ('I', 1, (1,3,1), True),
             ('J', 0, (5,), False),
             ('H', 1, (1,2,2), False),
             ('F', 1, (1,2,1), True),
             ('G', 0, (4,), False),
             ('E', 1, (1,1,2), False),
             ('C', 1, (1,1,1), True),
             ('D', 0, (3,), False),
             ('B', 0, (2,), False),
             ('A', 0, (1,),  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',
            [('A', 0, (2,), False),
             ('B', 0, (1,), 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',
            [('A', 0, (2,), False),
             ('B', 1, (1,3,2), False),
             ('C', 2, (1,4,1), True),
             ('D', 1, (1,3,1), True),
             ('E', 1, (1,1,2), False),
             ('F', 2, (1,2,1), True),
             ('G', 1, (1,1,1), True),
             ('H', 0, (1,), True),
             ],
            )

    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']},
            'C',
            [('C', 0, (2,), False),
             ('B', 1, (0,1,1), True),
             ('A', 0, (1,), 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': [],
             },
            'J',
            [('J', 0, (4,), False),
             ('I', 1, (1,3,2), False),
             ('H', 1, (1,3,1), True),
             ('G', 0, (3,), False),
             ('F', 1, (1,2,2), False),
             ('E', 1, (1,2,1), True),
             ('D', 0, (2,), False),
             ('C', 1, (1,1,2), False),
             ('B', 1, (1,1,1), True),
             ('A', 0, (1,), 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'],
            },
            'R',
            [('R', 0, (6,), False),
             ('Q', 1, (0,4,5), False),
             ('P', 2, (0,6,1), True),
             ('O', 1, (0,4,4), False),
             ('N', 1, (0,4,3), False),
             ('M', 2, (0,5,1), True),
             ('L', 1, (0,4,2), False),
             ('K', 1, (0,4,1), True),
             ('J', 0, (5,), False),
             ('I', 1, (0,3,1), True),
             ('H', 0, (4,), False),
             ('G', 1, (0,1,3), False),
             ('F', 2, (0,2,1), True),
             ('E', 1, (0,1,2), False),
             ('D', 1, (0,1,1), True),
             ('C', 0, (3,), False),
             ('B', 0, (2,), False),
             ('A', 0, (1,), True),
             ],
            )

    def test_ghost(self):
        # merge_sort should be able to ignore ghosts
        # A
        # |
        # B ghost
        # |/
        # C
        self.assertSortAndIterate(
            {'A': [],
             'B': ['A'],
             'C': ['B', 'ghost'],
            },
            'C',
            [('C', 0, (3,), False),
             ('B', 0, (2,), False),
             ('A', 0, (1,), True),
            ])

    def test_lefthand_ghost(self):
        # ghost
        #  |
        #  A
        #  |
        #  B
        self.assertSortAndIterate(
            {'A': ['ghost'],
             'B': ['A'],
            }, 'B',
            [('B', 0, (2,), False),
             ('A', 0, (1,), True),
            ])

    def test_graph_cycle(self):
        # merge_sort should fail with a simple error when a graph cycle is
        # encountered.
        #
        # A
        # |,-.
        # B  |
        # |  |
        # C  ^
        # |  |
        # D  |
        # |'-'
        # E
        self.assertRaises(errors.GraphCycleError,
            self.assertSortAndIterate,
                {'A': [],
                 'B': ['D'],
                 'C': ['B'],
                 'D': ['C'],
                 'E': ['D'],
                },
                'E',
                [])


class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
    """Test the sort order returned by gc_sort."""

    def assertSorted(self, expected, parent_map):
        graph = self.make_known_graph(parent_map)
        value = graph.gc_sort()
        if expected != value:
            self.assertEqualDiff(pprint.pformat(expected),
                                 pprint.pformat(value))

    def test_empty(self):
        self.assertSorted([], {})

    def test_single(self):
        self.assertSorted(['a'], {'a':()})
        self.assertSorted([('a',)], {('a',):()})
        self.assertSorted([('F', 'a')], {('F', 'a'):()})

    def test_linear(self):
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
        self.assertSorted([('c',), ('b',), ('a',)],
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
                           ('F', 'c'): (('F', 'b'),)})

    def test_mixed_ancestries(self):
        # Each prefix should be sorted separately
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
                          ],
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
                           ('F', 'c'): (('F', 'b'),),
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
                           ('G', 'c'): (('G', 'b'),),
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
                           ('Q', 'c'): (('Q', 'b'),),
                          })

    def test_stable_sorting(self):
        # the sort order should be stable even when extra nodes are added
        self.assertSorted(['b', 'c', 'a'],
                          {'a':(), 'b':('a',), 'c':('a',)})
        self.assertSorted(['b', 'c', 'd', 'a'],
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
        self.assertSorted(['b', 'c', 'd', 'a'],
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
                           'Z':('a',)})
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
                           'Z':('a',),
                           'e':('b', 'c', 'd'),
                           'f':('d', 'Z'),
                           })

    def test_skip_ghost(self):
        self.assertSorted(['b', 'c', 'a'],
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})

    def test_skip_mainline_ghost(self):
        self.assertSorted(['b', 'c', 'a'],
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})