← 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: Vincent Ladeuil
  • Date: 2009-06-18 14:12:37 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090618141237-k9u7mrithzstg15z
Replace the existing KnownGraph._find_gdfo.

* bzrlib/_known_graph_pyx.pyx:
(_find_gdfo): pyrex version, almost as fast as the previous one,
but we don't need the linear dominator so we can potentially save
some time during __init__.

* bzrlib/_known_graph_py.py:
(KnownGraph._find_gdfo): Get rid of the inner function to stay in
sync with the pyrex version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
 
1
# Copyright (C) 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Tests for the python and pyrex extensions of groupcompress"""
 
18
 
 
19
from bzrlib import (
 
20
    errors,
 
21
    graph as _mod_graph,
 
22
    _known_graph_py,
 
23
    tests,
 
24
    )
 
25
from bzrlib.tests import test_graph
 
26
from bzrlib.revision import NULL_REVISION
 
27
 
 
28
 
 
29
def load_tests(standard_tests, module, loader):
 
30
    """Parameterize tests for all versions of groupcompress."""
 
31
    scenarios = [
 
32
        ('python', {'module': _known_graph_py, 'do_cache': True}),
 
33
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
34
    ]
 
35
    suite = loader.suiteClass()
 
36
    if CompiledKnownGraphFeature.available():
 
37
        from bzrlib import _known_graph_pyx
 
38
        scenarios.append(('C', {'module': _known_graph_pyx, 'do_cache': True}))
 
39
        scenarios.append(('C-nocache',
 
40
                          {'module': _known_graph_pyx, 'do_cache': False}))
 
41
    else:
 
42
        # the compiled module isn't available, so we add a failing test
 
43
        class FailWithoutFeature(tests.TestCase):
 
44
            def test_fail(self):
 
45
                self.requireFeature(CompiledKnownGraphFeature)
 
46
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
 
47
    result = tests.multiply_tests(standard_tests, scenarios, suite)
 
48
    return result
 
49
 
 
50
 
 
51
class _CompiledKnownGraphFeature(tests.Feature):
 
52
 
 
53
    def _probe(self):
 
54
        try:
 
55
            import bzrlib._known_graph_pyx
 
56
        except ImportError:
 
57
            return False
 
58
        return True
 
59
 
 
60
    def feature_name(self):
 
61
        return 'bzrlib._known_graph_pyx'
 
62
 
 
63
CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
 
64
 
 
65
 
 
66
class TestKnownGraph(tests.TestCase):
 
67
 
 
68
    module = None # Set by load_tests
 
69
    do_cache = None # Set by load_tests
 
70
 
 
71
    def make_known_graph(self, ancestry):
 
72
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
 
73
 
 
74
    def assertDominator(self, graph, rev, dominator):
 
75
        node = graph._nodes[rev]
 
76
        self.assertEqual(dominator, node.linear_dominator)
 
77
 
 
78
    def assertGDFO(self, graph, rev, gdfo):
 
79
        node = graph._nodes[rev]
 
80
        self.assertEqual(gdfo, node.gdfo)
 
81
 
 
82
    def test_children_ancestry1(self):
 
83
        graph = self.make_known_graph(test_graph.ancestry_1)
 
84
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
 
85
        self.assertEqual(['rev2a', 'rev2b'],
 
86
                         sorted(graph._nodes['rev1'].child_keys))
 
87
        self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
 
88
        self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
 
89
        self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
 
90
 
 
91
    def test_dominators_ancestry_1(self):
 
92
        graph = self.make_known_graph(test_graph.ancestry_1)
 
93
        self.assertDominator(graph, 'rev1', NULL_REVISION)
 
94
        self.assertDominator(graph, 'rev2b', 'rev2b')
 
95
        self.assertDominator(graph, 'rev2a', 'rev2a')
 
96
        self.assertDominator(graph, 'rev3', 'rev2a')
 
97
        self.assertDominator(graph, 'rev4', 'rev4')
 
98
 
 
99
    def test_dominators_feature_branch(self):
 
100
        graph = self.make_known_graph(test_graph.feature_branch)
 
101
        self.assertDominator(graph, 'rev1', NULL_REVISION)
 
102
        self.assertDominator(graph, 'rev2b', NULL_REVISION)
 
103
        self.assertDominator(graph, 'rev3b', NULL_REVISION)
 
104
 
 
105
    def test_dominators_extended_history_shortcut(self):
 
106
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
107
        self.assertDominator(graph, 'a', NULL_REVISION)
 
108
        self.assertDominator(graph, 'b', 'b')
 
109
        self.assertDominator(graph, 'c', 'b')
 
110
        self.assertDominator(graph, 'd', 'b')
 
111
        self.assertDominator(graph, 'e', 'e')
 
112
        self.assertDominator(graph, 'f', 'f')
 
113
 
 
114
    def test_gdfo_ancestry_1(self):
 
115
        graph = self.make_known_graph(test_graph.ancestry_1)
 
116
        self.assertGDFO(graph, 'rev1', 2)
 
117
        self.assertGDFO(graph, 'rev2b', 3)
 
118
        self.assertGDFO(graph, 'rev2a', 3)
 
119
        self.assertGDFO(graph, 'rev3', 4)
 
120
        self.assertGDFO(graph, 'rev4', 5)
 
121
 
 
122
    def test_gdfo_feature_branch(self):
 
123
        graph = self.make_known_graph(test_graph.feature_branch)
 
124
        self.assertGDFO(graph, 'rev1', 2)
 
125
        self.assertGDFO(graph, 'rev2b', 3)
 
126
        self.assertGDFO(graph, 'rev3b', 4)
 
127
 
 
128
    def test_gdfo_extended_history_shortcut(self):
 
129
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
130
        self.assertGDFO(graph, 'a', 2)
 
131
        self.assertGDFO(graph, 'b', 3)
 
132
        self.assertGDFO(graph, 'c', 4)
 
133
        self.assertGDFO(graph, 'd', 5)
 
134
        self.assertGDFO(graph, 'e', 6)
 
135
        self.assertGDFO(graph, 'f', 6)
 
136
 
 
137
    def test_gdfo_with_ghost(self):
 
138
        graph = self.make_known_graph(test_graph.with_ghost)
 
139
        self.assertGDFO(graph, 'f', 2)
 
140
        self.assertGDFO(graph, 'e', 3)
 
141
        self.assertGDFO(graph, 'g', 1)
 
142
        self.assertGDFO(graph, 'b', 4)
 
143
        self.assertGDFO(graph, 'd', 4)
 
144
        self.assertGDFO(graph, 'a', 5)
 
145
        self.assertGDFO(graph, 'c', 5)
 
146
 
 
147
    def test_heads_null(self):
 
148
        graph = self.make_known_graph(test_graph.ancestry_1)
 
149
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
150
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
151
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
152
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
153
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
154
 
 
155
    def test_heads_one(self):
 
156
        # A single node will always be a head
 
157
        graph = self.make_known_graph(test_graph.ancestry_1)
 
158
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
159
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
160
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
161
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
162
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
163
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
164
 
 
165
    def test_heads_single(self):
 
166
        graph = self.make_known_graph(test_graph.ancestry_1)
 
167
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
168
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
169
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
170
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
171
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
 
172
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
173
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
174
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
175
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
176
 
 
177
    def test_heads_two_heads(self):
 
178
        graph = self.make_known_graph(test_graph.ancestry_1)
 
179
        self.assertEqual(set(['rev2a', 'rev2b']),
 
180
                         graph.heads(['rev2a', 'rev2b']))
 
181
        self.assertEqual(set(['rev3', 'rev2b']),
 
182
                         graph.heads(['rev3', 'rev2b']))
 
183
 
 
184
    def test_heads_criss_cross(self):
 
185
        graph = self.make_known_graph(test_graph.criss_cross)
 
186
        self.assertEqual(set(['rev2a']),
 
187
                         graph.heads(['rev2a', 'rev1']))
 
188
        self.assertEqual(set(['rev2b']),
 
189
                         graph.heads(['rev2b', 'rev1']))
 
190
        self.assertEqual(set(['rev3a']),
 
191
                         graph.heads(['rev3a', 'rev1']))
 
192
        self.assertEqual(set(['rev3b']),
 
193
                         graph.heads(['rev3b', 'rev1']))
 
194
        self.assertEqual(set(['rev2a', 'rev2b']),
 
195
                         graph.heads(['rev2a', 'rev2b']))
 
196
        self.assertEqual(set(['rev3a']),
 
197
                         graph.heads(['rev3a', 'rev2a']))
 
198
        self.assertEqual(set(['rev3a']),
 
199
                         graph.heads(['rev3a', 'rev2b']))
 
200
        self.assertEqual(set(['rev3a']),
 
201
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
202
        self.assertEqual(set(['rev3b']),
 
203
                         graph.heads(['rev3b', 'rev2a']))
 
204
        self.assertEqual(set(['rev3b']),
 
205
                         graph.heads(['rev3b', 'rev2b']))
 
206
        self.assertEqual(set(['rev3b']),
 
207
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
208
        self.assertEqual(set(['rev3a', 'rev3b']),
 
209
                         graph.heads(['rev3a', 'rev3b']))
 
210
        self.assertEqual(set(['rev3a', 'rev3b']),
 
211
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
212
 
 
213
    def test_heads_shortcut(self):
 
214
        graph = self.make_known_graph(test_graph.history_shortcut)
 
215
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
216
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
217
        self.assertEqual(set(['rev3a', 'rev3b']),
 
218
                         graph.heads(['rev3a', 'rev3b']))
 
219
        self.assertEqual(set(['rev3a', 'rev3b']),
 
220
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
221
        self.assertEqual(set(['rev2a', 'rev3b']),
 
222
                         graph.heads(['rev2a', 'rev3b']))
 
223
        self.assertEqual(set(['rev2c', 'rev3a']),
 
224
                         graph.heads(['rev2c', 'rev3a']))
 
225
 
 
226
    def test_heads_linear(self):
 
227
        graph = self.make_known_graph(test_graph.racing_shortcuts)
 
228
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
 
229
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
 
230
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
 
231
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
232
 
 
233
    def test_heads_with_ghost(self):
 
234
        graph = self.make_known_graph(test_graph.with_ghost)
 
235
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
236
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
 
237
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
 
238
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
 
239
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
 
240
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
 
241
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
 
242
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))