← 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: Tarmac
  • Author(s): Vincent Ladeuil
  • Date: 2017-01-30 14:42:05 UTC
  • mfrom: (6620.1.1 trunk)
  • Revision ID: tarmac-20170130144205-r8fh2xpmiuxyozpv
Merge  2.7 into trunk including fix for bug #1657238 [r=vila]

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010, 2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
20
20
 
21
21
from bzrlib import (
22
22
    errors,
23
 
    graph as _mod_graph,
24
23
    _known_graph_py,
25
24
    tests,
26
25
    )
27
26
from bzrlib.tests import test_graph
28
27
from bzrlib.revision import NULL_REVISION
29
 
 
30
 
 
31
 
def load_tests(standard_tests, module, loader):
32
 
    """Parameterize tests for all versions of groupcompress."""
 
28
from bzrlib.tests.scenarios import load_tests_apply_scenarios
 
29
from bzrlib.tests import (
 
30
    features,
 
31
    )
 
32
 
 
33
 
 
34
def caching_scenarios():
33
35
    scenarios = [
34
36
        ('python', {'module': _known_graph_py, 'do_cache': True}),
35
37
    ]
36
 
    caching_scenarios = [
 
38
    if compiled_known_graph_feature.available():
 
39
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
 
40
                                'do_cache': True}))
 
41
    return scenarios
 
42
 
 
43
 
 
44
def non_caching_scenarios():
 
45
    scenarios = [
37
46
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
38
47
    ]
39
 
    suite = loader.suiteClass()
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}))
45
 
    else:
46
 
        # the compiled module isn't available, so we add a failing test
47
 
        class FailWithoutFeature(tests.TestCase):
48
 
            def test_fail(self):
49
 
                self.requireFeature(CompiledKnownGraphFeature)
50
 
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
51
 
    # TestKnownGraphHeads needs to be permutated with and without caching.
52
 
    # All other TestKnownGraph tests only need to be tested across module
53
 
    heads_suite, other_suite = tests.split_suite_by_condition(
54
 
        standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
55
 
    suite = tests.multiply_tests(other_suite, scenarios, suite)
56
 
    suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
57
 
                                 suite)
58
 
    return suite
59
 
 
60
 
 
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()
 
48
    if compiled_known_graph_feature.available():
 
49
        scenarios.append(
 
50
            ('C-nocache', {'module': compiled_known_graph_feature.module,
 
51
                           'do_cache': False}))
 
52
    return scenarios
 
53
 
 
54
 
 
55
load_tests = load_tests_apply_scenarios
 
56
 
 
57
 
 
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
 
59
    'bzrlib._known_graph_pyx')
74
60
 
75
61
 
76
62
#  a
85
71
 
86
72
class TestCaseWithKnownGraph(tests.TestCase):
87
73
 
 
74
    scenarios = caching_scenarios()
88
75
    module = None # Set by load_tests
89
76
 
90
77
    def make_known_graph(self, ancestry):
99
86
 
100
87
    def test_children_ancestry1(self):
101
88
        graph = self.make_known_graph(test_graph.ancestry_1)
102
 
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
 
89
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
103
90
        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))
 
91
                         sorted(graph.get_child_keys('rev1')))
 
92
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
 
93
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
 
94
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
 
95
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
96
 
 
97
    def test_parent_ancestry1(self):
 
98
        graph = self.make_known_graph(test_graph.ancestry_1)
 
99
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
 
100
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
 
101
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
 
102
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
 
103
        self.assertEqual(['rev2b', 'rev3'],
 
104
                         sorted(graph.get_parent_keys('rev4')))
 
105
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
106
    
 
107
    def test_parent_with_ghost(self):
 
108
        graph = self.make_known_graph(test_graph.with_ghost)
 
109
        self.assertEqual(None, graph.get_parent_keys('g'))
108
110
 
109
111
    def test_gdfo_ancestry_1(self):
110
112
        graph = self.make_known_graph(test_graph.ancestry_1)
139
141
        self.assertGDFO(graph, 'a', 5)
140
142
        self.assertGDFO(graph, 'c', 5)
141
143
 
 
144
    def test_add_existing_node(self):
 
145
        graph = self.make_known_graph(test_graph.ancestry_1)
 
146
        # Add a node that already exists with identical content
 
147
        # This is a 'no-op'
 
148
        self.assertGDFO(graph, 'rev4', 5)
 
149
        graph.add_node('rev4', ['rev3', 'rev2b'])
 
150
        self.assertGDFO(graph, 'rev4', 5)
 
151
        # This also works if we use a tuple rather than a list
 
152
        graph.add_node('rev4', ('rev3', 'rev2b'))
 
153
 
 
154
    def test_add_existing_node_mismatched_parents(self):
 
155
        graph = self.make_known_graph(test_graph.ancestry_1)
 
156
        self.assertRaises(ValueError, graph.add_node, 'rev4',
 
157
                          ['rev2b', 'rev3'])
 
158
 
 
159
    def test_add_node_with_ghost_parent(self):
 
160
        graph = self.make_known_graph(test_graph.ancestry_1)
 
161
        graph.add_node('rev5', ['rev2b', 'revGhost'])
 
162
        self.assertGDFO(graph, 'rev5', 4)
 
163
        self.assertGDFO(graph, 'revGhost', 1)
 
164
 
 
165
    def test_add_new_root(self):
 
166
        graph = self.make_known_graph(test_graph.ancestry_1)
 
167
        graph.add_node('rev5', [])
 
168
        self.assertGDFO(graph, 'rev5', 1)
 
169
 
 
170
    def test_add_with_all_ghost_parents(self):
 
171
        graph = self.make_known_graph(test_graph.ancestry_1)
 
172
        graph.add_node('rev5', ['ghost'])
 
173
        self.assertGDFO(graph, 'rev5', 2)
 
174
        self.assertGDFO(graph, 'ghost', 1)
 
175
 
 
176
    def test_gdfo_after_add_node(self):
 
177
        graph = self.make_known_graph(test_graph.ancestry_1)
 
178
        self.assertEqual([], graph.get_child_keys('rev4'))
 
179
        graph.add_node('rev5', ['rev4'])
 
180
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
 
181
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
 
182
        self.assertEqual([], graph.get_child_keys('rev5'))
 
183
        self.assertGDFO(graph, 'rev5', 6)
 
184
        graph.add_node('rev6', ['rev2b'])
 
185
        graph.add_node('rev7', ['rev6'])
 
186
        graph.add_node('rev8', ['rev7', 'rev5'])
 
187
        self.assertGDFO(graph, 'rev5', 6)
 
188
        self.assertGDFO(graph, 'rev6', 4)
 
189
        self.assertGDFO(graph, 'rev7', 5)
 
190
        self.assertGDFO(graph, 'rev8', 7)
 
191
 
 
192
    def test_fill_in_ghost(self):
 
193
        graph = self.make_known_graph(test_graph.with_ghost)
 
194
        # Add in a couple nodes and then fill in the 'ghost' so that it should
 
195
        # cause renumbering of children nodes
 
196
        graph.add_node('x', [])
 
197
        graph.add_node('y', ['x'])
 
198
        graph.add_node('z', ['y'])
 
199
        graph.add_node('g', ['z'])
 
200
        self.assertGDFO(graph, 'f', 2)
 
201
        self.assertGDFO(graph, 'e', 3)
 
202
        self.assertGDFO(graph, 'x', 1)
 
203
        self.assertGDFO(graph, 'y', 2)
 
204
        self.assertGDFO(graph, 'z', 3)
 
205
        self.assertGDFO(graph, 'g', 4)
 
206
        self.assertGDFO(graph, 'b', 4)
 
207
        self.assertGDFO(graph, 'd', 5)
 
208
        self.assertGDFO(graph, 'a', 5)
 
209
        self.assertGDFO(graph, 'c', 6)
 
210
 
142
211
 
143
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
144
213
 
 
214
    scenarios = caching_scenarios() + non_caching_scenarios()
145
215
    do_cache = None # Set by load_tests
146
216
 
147
217
    def test_heads_null(self):
245
315
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
246
316
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
247
317
 
 
318
    def test_filling_in_ghosts_resets_head_cache(self):
 
319
        graph = self.make_known_graph(test_graph.with_ghost)
 
320
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
 
322
        # different
 
323
        graph.add_node('g', ['e'])
 
324
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
 
325
 
248
326
 
249
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
250
328
 
731
809
             ('A', 0, (1,), True),
732
810
            ])
733
811
 
 
812
    def test_lefthand_ghost(self):
 
813
        # ghost
 
814
        #  |
 
815
        #  A
 
816
        #  |
 
817
        #  B
 
818
        self.assertSortAndIterate(
 
819
            {'A': ['ghost'],
 
820
             'B': ['A'],
 
821
            }, 'B',
 
822
            [('B', 0, (2,), False),
 
823
             ('A', 0, (1,), True),
 
824
            ])
 
825
 
734
826
    def test_graph_cycle(self):
735
827
        # merge_sort should fail with a simple error when a graph cycle is
736
828
        # encountered.
754
846
                },
755
847
                'E',
756
848
                [])
 
849
 
 
850
 
 
851
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
852
    """Test the sort order returned by gc_sort."""
 
853
 
 
854
    def assertSorted(self, expected, parent_map):
 
855
        graph = self.make_known_graph(parent_map)
 
856
        value = graph.gc_sort()
 
857
        if expected != value:
 
858
            self.assertEqualDiff(pprint.pformat(expected),
 
859
                                 pprint.pformat(value))
 
860
 
 
861
    def test_empty(self):
 
862
        self.assertSorted([], {})
 
863
 
 
864
    def test_single(self):
 
865
        self.assertSorted(['a'], {'a':()})
 
866
        self.assertSorted([('a',)], {('a',):()})
 
867
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
868
 
 
869
    def test_linear(self):
 
870
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
871
        self.assertSorted([('c',), ('b',), ('a',)],
 
872
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
873
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
874
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
875
                           ('F', 'c'): (('F', 'b'),)})
 
876
 
 
877
    def test_mixed_ancestries(self):
 
878
        # Each prefix should be sorted separately
 
879
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
882
                          ],
 
883
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
884
                           ('F', 'c'): (('F', 'b'),),
 
885
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
886
                           ('G', 'c'): (('G', 'b'),),
 
887
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
888
                           ('Q', 'c'): (('Q', 'b'),),
 
889
                          })
 
890
 
 
891
    def test_stable_sorting(self):
 
892
        # the sort order should be stable even when extra nodes are added
 
893
        self.assertSorted(['b', 'c', 'a'],
 
894
                          {'a':(), 'b':('a',), 'c':('a',)})
 
895
        self.assertSorted(['b', 'c', 'd', 'a'],
 
896
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
897
        self.assertSorted(['b', 'c', 'd', 'a'],
 
898
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
899
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
900
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
901
                           'Z':('a',)})
 
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
903
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
904
                           'Z':('a',),
 
905
                           'e':('b', 'c', 'd'),
 
906
                           'f':('d', 'Z'),
 
907
                           })
 
908
 
 
909
    def test_skip_ghost(self):
 
910
        self.assertSorted(['b', 'c', 'a'],
 
911
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
912
 
 
913
    def test_skip_mainline_ghost(self):
 
914
        self.assertSorted(['b', 'c', 'a'],
 
915
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})