← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-11-30 22:04:45 UTC
  • mfrom: (4789.28.4 2.1.0b4-builder-no-keys)
  • Revision ID: pqm@pqm.ubuntu.com-20091130220445-vbfmmgocbgcs195q
(jam) Update BTreeBuilder to remove ._keys and use StaticTuple

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
99
99
 
100
100
    def test_children_ancestry1(self):
101
101
        graph = self.make_known_graph(test_graph.ancestry_1)
102
 
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
 
102
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
103
103
        self.assertEqual(['rev2a', 'rev2b'],
104
 
                         sorted(graph._nodes['rev1'].child_keys))
105
 
        self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
106
 
        self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
107
 
        self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
 
104
                         sorted(graph.get_child_keys('rev1')))
 
105
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
 
106
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
 
107
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
 
108
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
109
 
 
110
    def test_parent_ancestry1(self):
 
111
        graph = self.make_known_graph(test_graph.ancestry_1)
 
112
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
 
113
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
 
114
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
 
115
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
 
116
        self.assertEqual(['rev2b', 'rev3'],
 
117
                         sorted(graph.get_parent_keys('rev4')))
 
118
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
119
    
 
120
    def test_parent_with_ghost(self):
 
121
        graph = self.make_known_graph(test_graph.with_ghost)
 
122
        self.assertEqual(None, graph.get_parent_keys('g'))
108
123
 
109
124
    def test_gdfo_ancestry_1(self):
110
125
        graph = self.make_known_graph(test_graph.ancestry_1)
768
783
                },
769
784
                'E',
770
785
                [])
 
786
 
 
787
 
 
788
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
789
    """Test the sort order returned by gc_sort."""
 
790
 
 
791
    def assertSorted(self, expected, parent_map):
 
792
        graph = self.make_known_graph(parent_map)
 
793
        value = graph.gc_sort()
 
794
        if expected != value:
 
795
            self.assertEqualDiff(pprint.pformat(expected),
 
796
                                 pprint.pformat(value))
 
797
 
 
798
    def test_empty(self):
 
799
        self.assertSorted([], {})
 
800
 
 
801
    def test_single(self):
 
802
        self.assertSorted(['a'], {'a':()})
 
803
        self.assertSorted([('a',)], {('a',):()})
 
804
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
805
 
 
806
    def test_linear(self):
 
807
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
808
        self.assertSorted([('c',), ('b',), ('a',)],
 
809
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
810
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
811
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
812
                           ('F', 'c'): (('F', 'b'),)})
 
813
 
 
814
    def test_mixed_ancestries(self):
 
815
        # Each prefix should be sorted separately
 
816
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
817
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
818
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
819
                          ],
 
820
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
821
                           ('F', 'c'): (('F', 'b'),),
 
822
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
823
                           ('G', 'c'): (('G', 'b'),),
 
824
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
825
                           ('Q', 'c'): (('Q', 'b'),),
 
826
                          })
 
827
 
 
828
    def test_stable_sorting(self):
 
829
        # the sort order should be stable even when extra nodes are added
 
830
        self.assertSorted(['b', 'c', 'a'],
 
831
                          {'a':(), 'b':('a',), 'c':('a',)})
 
832
        self.assertSorted(['b', 'c', 'd', 'a'],
 
833
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
834
        self.assertSorted(['b', 'c', 'd', 'a'],
 
835
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
836
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
837
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
838
                           'Z':('a',)})
 
839
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
840
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
841
                           'Z':('a',),
 
842
                           'e':('b', 'c', 'd'),
 
843
                           'f':('d', 'Z'),
 
844
                           })
 
845
 
 
846
    def test_skip_ghost(self):
 
847
        self.assertSorted(['b', 'c', 'a'],
 
848
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
849
 
 
850
    def test_skip_mainline_ghost(self):
 
851
        self.assertSorted(['b', 'c', 'a'],
 
852
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})