← 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: Robert Collins
  • Date: 2009-08-04 04:36:34 UTC
  • mfrom: (4583 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4593.
  • Revision ID: robertc@robertcollins.net-20090804043634-2iu9wpcgs273i97s
Merge bzr.dev.

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