/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-10 18:58:02 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090610185802-wsybzjfil447yhy2
Change VF.annotate to use the new KnownGraph code.

This shows a significant savings in the time for 'annotate NEWS', of about 5s/20s
for knit formats, and 45s => 20s for GC formats.


Also, factor the code into a helper, so that we can prepare for writing
a 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, distance):
 
75
        node = graph._nodes[rev]
 
76
        self.assertEqual(dominator, node.linear_dominator)
 
77
        self.assertEqual(distance, node.dominator_distance)
 
78
 
 
79
    def assertGDFO(self, graph, rev, gdfo):
 
80
        node = graph._nodes[rev]
 
81
        self.assertEqual(gdfo, node.gdfo)
 
82
 
 
83
    def test_children_ancestry1(self):
 
84
        graph = self.make_known_graph(test_graph.ancestry_1)
 
85
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
 
86
        self.assertEqual(['rev2a', 'rev2b'],
 
87
                         sorted(graph._nodes['rev1'].child_keys))
 
88
        self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
 
89
        self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
 
90
        self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
 
91
 
 
92
    def test_dominators_ancestry_1(self):
 
93
        graph = self.make_known_graph(test_graph.ancestry_1)
 
94
        self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
 
95
        self.assertDominator(graph, 'rev2b', 'rev2b', 0)
 
96
        self.assertDominator(graph, 'rev2a', 'rev2a', 0)
 
97
        self.assertDominator(graph, 'rev3', 'rev2a', 1)
 
98
        self.assertDominator(graph, 'rev4', 'rev4', 0)
 
99
 
 
100
    def test_dominators_feature_branch(self):
 
101
        graph = self.make_known_graph(test_graph.feature_branch)
 
102
        self.assertDominator(graph, 'rev1', NULL_REVISION, 1)
 
103
        self.assertDominator(graph, 'rev2b', NULL_REVISION, 2)
 
104
        self.assertDominator(graph, 'rev3b', NULL_REVISION, 3)
 
105
 
 
106
    def test_dominators_extended_history_shortcut(self):
 
107
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
108
        self.assertDominator(graph, 'a', NULL_REVISION, 1)
 
109
        self.assertDominator(graph, 'b', 'b', 0)
 
110
        self.assertDominator(graph, 'c', 'b', 1)
 
111
        self.assertDominator(graph, 'd', 'b', 2)
 
112
        self.assertDominator(graph, 'e', 'e', 0)
 
113
        self.assertDominator(graph, 'f', 'f', 0)
 
114
 
 
115
    def test_gdfo_ancestry_1(self):
 
116
        graph = self.make_known_graph(test_graph.ancestry_1)
 
117
        self.assertGDFO(graph, 'rev1', 2)
 
118
        self.assertGDFO(graph, 'rev2b', 3)
 
119
        self.assertGDFO(graph, 'rev2a', 3)
 
120
        self.assertGDFO(graph, 'rev3', 4)
 
121
        self.assertGDFO(graph, 'rev4', 5)
 
122
 
 
123
    def test_gdfo_feature_branch(self):
 
124
        graph = self.make_known_graph(test_graph.feature_branch)
 
125
        self.assertGDFO(graph, 'rev1', 2)
 
126
        self.assertGDFO(graph, 'rev2b', 3)
 
127
        self.assertGDFO(graph, 'rev3b', 4)
 
128
 
 
129
    def test_gdfo_extended_history_shortcut(self):
 
130
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
131
        self.assertGDFO(graph, 'a', 2)
 
132
        self.assertGDFO(graph, 'b', 3)
 
133
        self.assertGDFO(graph, 'c', 4)
 
134
        self.assertGDFO(graph, 'd', 5)
 
135
        self.assertGDFO(graph, 'e', 6)
 
136
        self.assertGDFO(graph, 'f', 6)
 
137
 
 
138
    def test_gdfo_with_ghost(self):
 
139
        graph = self.make_known_graph(test_graph.with_ghost)
 
140
        self.assertGDFO(graph, 'f', 2)
 
141
        self.assertGDFO(graph, 'e', 3)
 
142
        self.assertGDFO(graph, 'g', 1)
 
143
        self.assertGDFO(graph, 'b', 4)
 
144
        self.assertGDFO(graph, 'd', 4)
 
145
        self.assertGDFO(graph, 'a', 5)
 
146
        self.assertGDFO(graph, 'c', 5)
 
147
 
 
148
    def test_heads_null(self):
 
149
        graph = self.make_known_graph(test_graph.ancestry_1)
 
150
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
151
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
152
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
153
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
154
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
155
 
 
156
    def test_heads_one(self):
 
157
        # A single node will always be a head
 
158
        graph = self.make_known_graph(test_graph.ancestry_1)
 
159
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
160
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
161
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
162
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
163
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
164
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
165
 
 
166
    def test_heads_single(self):
 
167
        graph = self.make_known_graph(test_graph.ancestry_1)
 
168
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
169
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
170
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
171
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
172
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
 
173
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
174
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
175
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
176
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
177
 
 
178
    def test_heads_two_heads(self):
 
179
        graph = self.make_known_graph(test_graph.ancestry_1)
 
180
        self.assertEqual(set(['rev2a', 'rev2b']),
 
181
                         graph.heads(['rev2a', 'rev2b']))
 
182
        self.assertEqual(set(['rev3', 'rev2b']),
 
183
                         graph.heads(['rev3', 'rev2b']))
 
184
 
 
185
    def test_heads_criss_cross(self):
 
186
        graph = self.make_known_graph(test_graph.criss_cross)
 
187
        self.assertEqual(set(['rev2a']),
 
188
                         graph.heads(['rev2a', 'rev1']))
 
189
        self.assertEqual(set(['rev2b']),
 
190
                         graph.heads(['rev2b', 'rev1']))
 
191
        self.assertEqual(set(['rev3a']),
 
192
                         graph.heads(['rev3a', 'rev1']))
 
193
        self.assertEqual(set(['rev3b']),
 
194
                         graph.heads(['rev3b', 'rev1']))
 
195
        self.assertEqual(set(['rev2a', 'rev2b']),
 
196
                         graph.heads(['rev2a', 'rev2b']))
 
197
        self.assertEqual(set(['rev3a']),
 
198
                         graph.heads(['rev3a', 'rev2a']))
 
199
        self.assertEqual(set(['rev3a']),
 
200
                         graph.heads(['rev3a', 'rev2b']))
 
201
        self.assertEqual(set(['rev3a']),
 
202
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
203
        self.assertEqual(set(['rev3b']),
 
204
                         graph.heads(['rev3b', 'rev2a']))
 
205
        self.assertEqual(set(['rev3b']),
 
206
                         graph.heads(['rev3b', 'rev2b']))
 
207
        self.assertEqual(set(['rev3b']),
 
208
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
209
        self.assertEqual(set(['rev3a', 'rev3b']),
 
210
                         graph.heads(['rev3a', 'rev3b']))
 
211
        self.assertEqual(set(['rev3a', 'rev3b']),
 
212
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
213
 
 
214
    def test_heads_shortcut(self):
 
215
        graph = self.make_known_graph(test_graph.history_shortcut)
 
216
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
217
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
218
        self.assertEqual(set(['rev3a', 'rev3b']),
 
219
                         graph.heads(['rev3a', 'rev3b']))
 
220
        self.assertEqual(set(['rev3a', 'rev3b']),
 
221
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
222
        self.assertEqual(set(['rev2a', 'rev3b']),
 
223
                         graph.heads(['rev2a', 'rev3b']))
 
224
        self.assertEqual(set(['rev2c', 'rev3a']),
 
225
                         graph.heads(['rev2c', 'rev3a']))
 
226
 
 
227
 
 
228