« back to all changes in this revision
Viewing changes to bzrlib/tests/test__known_graph.py
- browse files at revision 4449
- compare with another revision
- compare with revision 334
- download diff
- download tarball
- view history from revision 4449
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-06-16 19:32:32 UTC
- mfrom: (4371.3.48 1.16-better_heads)
- Revision ID: pqm@pqm.ubuntu.com-20090616193232-rorncr6v3z633n9u
(jam) graph.KnownGraph implementation,
used for optimized heads() lookups during annotate.
used for optimized heads() lookups during annotate.
added
removed
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']))
Loggerhead is a web-based interface for Breezy
Version: 2.0.1