← 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: Ian Clatworthy
  • Date: 2009-09-02 16:03:51 UTC
  • mto: (4634.39.1 pdf-chm-docs)
  • mto: This revision was merged to the branch mainline in revision 4689.
  • Revision ID: ian.clatworthy@canonical.com-20090902160351-sxptcz3ttc1aencw
first cut at pdf docs via sphinx

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
37
37
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
38
38
    ]
39
39
    suite = loader.suiteClass()
40
 
    if compiled_known_graph_feature.available():
41
 
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
42
 
                                'do_cache': True}))
43
 
        caching_scenarios.append(
44
 
            ('C-nocache', {'module': compiled_known_graph_feature.module,
45
 
                           'do_cache': False}))
 
40
    if CompiledKnownGraphFeature.available():
 
41
        from bzrlib import _known_graph_pyx
 
42
        scenarios.append(('C', {'module': _known_graph_pyx, 'do_cache': True}))
 
43
        caching_scenarios.append(('C-nocache',
 
44
                          {'module': _known_graph_pyx, 'do_cache': False}))
46
45
    else:
47
46
        # the compiled module isn't available, so we add a failing test
48
47
        class FailWithoutFeature(tests.TestCase):
49
48
            def test_fail(self):
50
 
                self.requireFeature(compiled_known_graph_feature)
 
49
                self.requireFeature(CompiledKnownGraphFeature)
51
50
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
52
51
    # TestKnownGraphHeads needs to be permutated with and without caching.
53
52
    # All other TestKnownGraph tests only need to be tested across module
59
58
    return suite
60
59
 
61
60
 
62
 
compiled_known_graph_feature = tests.ModuleAvailableFeature(
63
 
                                    'bzrlib._known_graph_pyx')
 
61
class _CompiledKnownGraphFeature(tests.Feature):
 
62
 
 
63
    def _probe(self):
 
64
        try:
 
65
            import bzrlib._known_graph_pyx
 
66
        except ImportError:
 
67
            return False
 
68
        return True
 
69
 
 
70
    def feature_name(self):
 
71
        return 'bzrlib._known_graph_pyx'
 
72
 
 
73
CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
64
74
 
65
75
 
66
76
#  a
89
99
 
90
100
    def test_children_ancestry1(self):
91
101
        graph = self.make_known_graph(test_graph.ancestry_1)
92
 
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
 
102
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
93
103
        self.assertEqual(['rev2a', 'rev2b'],
94
 
                         sorted(graph.get_child_keys('rev1')))
95
 
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
96
 
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
97
 
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
98
 
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
99
 
 
100
 
    def test_parent_ancestry1(self):
101
 
        graph = self.make_known_graph(test_graph.ancestry_1)
102
 
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
103
 
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
104
 
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
105
 
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
106
 
        self.assertEqual(['rev2b', 'rev3'],
107
 
                         sorted(graph.get_parent_keys('rev4')))
108
 
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
109
 
    
110
 
    def test_parent_with_ghost(self):
111
 
        graph = self.make_known_graph(test_graph.with_ghost)
112
 
        self.assertEqual(None, graph.get_parent_keys('g'))
 
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))
113
108
 
114
109
    def test_gdfo_ancestry_1(self):
115
110
        graph = self.make_known_graph(test_graph.ancestry_1)
144
139
        self.assertGDFO(graph, 'a', 5)
145
140
        self.assertGDFO(graph, 'c', 5)
146
141
 
147
 
    def test_add_existing_node(self):
148
 
        graph = self.make_known_graph(test_graph.ancestry_1)
149
 
        # Add a node that already exists with identical content
150
 
        # This is a 'no-op'
151
 
        self.assertGDFO(graph, 'rev4', 5)
152
 
        graph.add_node('rev4', ['rev3', 'rev2b'])
153
 
        self.assertGDFO(graph, 'rev4', 5)
154
 
        # This also works if we use a tuple rather than a list
155
 
        graph.add_node('rev4', ('rev3', 'rev2b'))
156
 
 
157
 
    def test_add_existing_node_mismatched_parents(self):
158
 
        graph = self.make_known_graph(test_graph.ancestry_1)
159
 
        self.assertRaises(ValueError, graph.add_node, 'rev4',
160
 
                          ['rev2b', 'rev3'])
161
 
 
162
 
    def test_add_node_with_ghost_parent(self):
163
 
        graph = self.make_known_graph(test_graph.ancestry_1)
164
 
        graph.add_node('rev5', ['rev2b', 'revGhost'])
165
 
        self.assertGDFO(graph, 'rev5', 4)
166
 
        self.assertGDFO(graph, 'revGhost', 1)
167
 
 
168
 
    def test_add_new_root(self):
169
 
        graph = self.make_known_graph(test_graph.ancestry_1)
170
 
        graph.add_node('rev5', [])
171
 
        self.assertGDFO(graph, 'rev5', 1)
172
 
 
173
 
    def test_add_with_all_ghost_parents(self):
174
 
        graph = self.make_known_graph(test_graph.ancestry_1)
175
 
        graph.add_node('rev5', ['ghost'])
176
 
        self.assertGDFO(graph, 'rev5', 2)
177
 
        self.assertGDFO(graph, 'ghost', 1)
178
 
 
179
 
    def test_gdfo_after_add_node(self):
180
 
        graph = self.make_known_graph(test_graph.ancestry_1)
181
 
        self.assertEqual([], graph.get_child_keys('rev4'))
182
 
        graph.add_node('rev5', ['rev4'])
183
 
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
184
 
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
185
 
        self.assertEqual([], graph.get_child_keys('rev5'))
186
 
        self.assertGDFO(graph, 'rev5', 6)
187
 
        graph.add_node('rev6', ['rev2b'])
188
 
        graph.add_node('rev7', ['rev6'])
189
 
        graph.add_node('rev8', ['rev7', 'rev5'])
190
 
        self.assertGDFO(graph, 'rev5', 6)
191
 
        self.assertGDFO(graph, 'rev6', 4)
192
 
        self.assertGDFO(graph, 'rev7', 5)
193
 
        self.assertGDFO(graph, 'rev8', 7)
194
 
 
195
 
    def test_fill_in_ghost(self):
196
 
        graph = self.make_known_graph(test_graph.with_ghost)
197
 
        # Add in a couple nodes and then fill in the 'ghost' so that it should
198
 
        # cause renumbering of children nodes
199
 
        graph.add_node('x', [])
200
 
        graph.add_node('y', ['x'])
201
 
        graph.add_node('z', ['y'])
202
 
        graph.add_node('g', ['z'])
203
 
        self.assertGDFO(graph, 'f', 2)
204
 
        self.assertGDFO(graph, 'e', 3)
205
 
        self.assertGDFO(graph, 'x', 1)
206
 
        self.assertGDFO(graph, 'y', 2)
207
 
        self.assertGDFO(graph, 'z', 3)
208
 
        self.assertGDFO(graph, 'g', 4)
209
 
        self.assertGDFO(graph, 'b', 4)
210
 
        self.assertGDFO(graph, 'd', 5)
211
 
        self.assertGDFO(graph, 'a', 5)
212
 
        self.assertGDFO(graph, 'c', 6)
213
 
 
214
142
 
215
143
class TestKnownGraphHeads(TestCaseWithKnownGraph):
216
144
 
317
245
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
318
246
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
319
247
 
320
 
    def test_filling_in_ghosts_resets_head_cache(self):
321
 
        graph = self.make_known_graph(test_graph.with_ghost)
322
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
323
 
        # 'g' is filled in, and decends from 'e', so the heads result is now
324
 
        # different
325
 
        graph.add_node('g', ['e'])
326
 
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
327
 
 
328
248
 
329
249
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
330
250
 
848
768
                },
849
769
                'E',
850
770
                [])
851
 
 
852
 
 
853
 
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
854
 
    """Test the sort order returned by gc_sort."""
855
 
 
856
 
    def assertSorted(self, expected, parent_map):
857
 
        graph = self.make_known_graph(parent_map)
858
 
        value = graph.gc_sort()
859
 
        if expected != value:
860
 
            self.assertEqualDiff(pprint.pformat(expected),
861
 
                                 pprint.pformat(value))
862
 
 
863
 
    def test_empty(self):
864
 
        self.assertSorted([], {})
865
 
 
866
 
    def test_single(self):
867
 
        self.assertSorted(['a'], {'a':()})
868
 
        self.assertSorted([('a',)], {('a',):()})
869
 
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
870
 
 
871
 
    def test_linear(self):
872
 
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
873
 
        self.assertSorted([('c',), ('b',), ('a',)],
874
 
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
875
 
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
876
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
877
 
                           ('F', 'c'): (('F', 'b'),)})
878
 
 
879
 
    def test_mixed_ancestries(self):
880
 
        # Each prefix should be sorted separately
881
 
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
882
 
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
883
 
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
884
 
                          ],
885
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
886
 
                           ('F', 'c'): (('F', 'b'),),
887
 
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
888
 
                           ('G', 'c'): (('G', 'b'),),
889
 
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
890
 
                           ('Q', 'c'): (('Q', 'b'),),
891
 
                          })
892
 
 
893
 
    def test_stable_sorting(self):
894
 
        # the sort order should be stable even when extra nodes are added
895
 
        self.assertSorted(['b', 'c', 'a'],
896
 
                          {'a':(), 'b':('a',), 'c':('a',)})
897
 
        self.assertSorted(['b', 'c', 'd', 'a'],
898
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
899
 
        self.assertSorted(['b', 'c', 'd', 'a'],
900
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
901
 
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
902
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
903
 
                           'Z':('a',)})
904
 
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
905
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
906
 
                           'Z':('a',),
907
 
                           'e':('b', 'c', 'd'),
908
 
                           'f':('d', 'Z'),
909
 
                           })
910
 
 
911
 
    def test_skip_ghost(self):
912
 
        self.assertSorted(['b', 'c', 'a'],
913
 
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
914
 
 
915
 
    def test_skip_mainline_ghost(self):
916
 
        self.assertSorted(['b', 'c', 'a'],
917
 
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})