/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 breezy/tests/test__known_graph.py

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test__known_graph.py
1
 
# Copyright (C) 2009, 2010 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
18
18
 
19
19
import pprint
20
20
 
21
 
from bzrlib import (
 
21
from .. import (
22
22
    errors,
23
 
    graph as _mod_graph,
24
23
    _known_graph_py,
25
24
    tests,
26
25
    )
27
 
from bzrlib.tests import test_graph
28
 
from bzrlib.revision import NULL_REVISION
29
 
 
30
 
 
31
 
def load_tests(standard_tests, module, loader):
32
 
    """Parameterize tests for all versions of groupcompress."""
 
26
from . import test_graph
 
27
from ..revision import NULL_REVISION
 
28
from .scenarios import load_tests_apply_scenarios
 
29
from . 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 = [
37
 
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
38
 
    ]
39
 
    suite = loader.suiteClass()
40
38
    if compiled_known_graph_feature.available():
41
39
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
42
40
                                'do_cache': True}))
43
 
        caching_scenarios.append(
 
41
    return scenarios
 
42
 
 
43
 
 
44
def non_caching_scenarios():
 
45
    scenarios = [
 
46
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
47
    ]
 
48
    if compiled_known_graph_feature.available():
 
49
        scenarios.append(
44
50
            ('C-nocache', {'module': compiled_known_graph_feature.module,
45
51
                           'do_cache': False}))
46
 
    else:
47
 
        # the compiled module isn't available, so we add a failing test
48
 
        class FailWithoutFeature(tests.TestCase):
49
 
            def test_fail(self):
50
 
                self.requireFeature(compiled_known_graph_feature)
51
 
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
52
 
    # TestKnownGraphHeads needs to be permutated with and without caching.
53
 
    # All other TestKnownGraph tests only need to be tested across module
54
 
    heads_suite, other_suite = tests.split_suite_by_condition(
55
 
        standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
56
 
    suite = tests.multiply_tests(other_suite, scenarios, suite)
57
 
    suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
58
 
                                 suite)
59
 
    return suite
60
 
 
61
 
 
62
 
compiled_known_graph_feature = tests.ModuleAvailableFeature(
63
 
                                    'bzrlib._known_graph_pyx')
 
52
    return scenarios
 
53
 
 
54
 
 
55
load_tests = load_tests_apply_scenarios
 
56
 
 
57
 
 
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
 
59
    'breezy._known_graph_pyx')
64
60
 
65
61
 
66
62
#  a
70
66
#  c |
71
67
#   \|
72
68
#    d
73
 
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
 
69
alt_merge = {b'a': [], b'b': [b'a'], b'c': [b'b'], b'd': [b'a', b'c']}
74
70
 
75
71
 
76
72
class TestCaseWithKnownGraph(tests.TestCase):
77
73
 
78
 
    module = None # Set by load_tests
 
74
    scenarios = caching_scenarios()
 
75
    module = None  # Set by load_tests
79
76
 
80
77
    def make_known_graph(self, ancestry):
81
78
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
89
86
 
90
87
    def test_children_ancestry1(self):
91
88
        graph = self.make_known_graph(test_graph.ancestry_1)
92
 
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
93
 
        self.assertEqual(['rev2a', 'rev2b'],
94
 
                         sorted(graph.get_child_keys('rev1')))
95
 
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
96
 
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
97
 
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
98
 
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
89
        self.assertEqual([b'rev1'], graph.get_child_keys(NULL_REVISION))
 
90
        self.assertEqual([b'rev2a', b'rev2b'],
 
91
                         sorted(graph.get_child_keys(b'rev1')))
 
92
        self.assertEqual([b'rev3'], graph.get_child_keys(b'rev2a'))
 
93
        self.assertEqual([b'rev4'], graph.get_child_keys(b'rev3'))
 
94
        self.assertEqual([b'rev4'], graph.get_child_keys(b'rev2b'))
 
95
        self.assertRaises(KeyError, graph.get_child_keys, b'not_in_graph')
99
96
 
100
97
    def test_parent_ancestry1(self):
101
98
        graph = self.make_known_graph(test_graph.ancestry_1)
102
 
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
103
 
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
104
 
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
105
 
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
106
 
        self.assertEqual(['rev2b', 'rev3'],
107
 
                         sorted(graph.get_parent_keys('rev4')))
108
 
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
109
 
    
 
99
        self.assertEqual([NULL_REVISION], graph.get_parent_keys(b'rev1'))
 
100
        self.assertEqual([b'rev1'], graph.get_parent_keys(b'rev2a'))
 
101
        self.assertEqual([b'rev1'], graph.get_parent_keys(b'rev2b'))
 
102
        self.assertEqual([b'rev2a'], graph.get_parent_keys(b'rev3'))
 
103
        self.assertEqual([b'rev2b', b'rev3'],
 
104
                         sorted(graph.get_parent_keys(b'rev4')))
 
105
        self.assertRaises(KeyError, graph.get_child_keys, b'not_in_graph')
 
106
 
110
107
    def test_parent_with_ghost(self):
111
108
        graph = self.make_known_graph(test_graph.with_ghost)
112
 
        self.assertEqual(None, graph.get_parent_keys('g'))
 
109
        self.assertEqual(None, graph.get_parent_keys(b'g'))
113
110
 
114
111
    def test_gdfo_ancestry_1(self):
115
112
        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)
 
113
        self.assertGDFO(graph, b'rev1', 2)
 
114
        self.assertGDFO(graph, b'rev2b', 3)
 
115
        self.assertGDFO(graph, b'rev2a', 3)
 
116
        self.assertGDFO(graph, b'rev3', 4)
 
117
        self.assertGDFO(graph, b'rev4', 5)
121
118
 
122
119
    def test_gdfo_feature_branch(self):
123
120
        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)
 
121
        self.assertGDFO(graph, b'rev1', 2)
 
122
        self.assertGDFO(graph, b'rev2b', 3)
 
123
        self.assertGDFO(graph, b'rev3b', 4)
127
124
 
128
125
    def test_gdfo_extended_history_shortcut(self):
129
126
        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)
 
127
        self.assertGDFO(graph, b'a', 2)
 
128
        self.assertGDFO(graph, b'b', 3)
 
129
        self.assertGDFO(graph, b'c', 4)
 
130
        self.assertGDFO(graph, b'd', 5)
 
131
        self.assertGDFO(graph, b'e', 6)
 
132
        self.assertGDFO(graph, b'f', 6)
136
133
 
137
134
    def test_gdfo_with_ghost(self):
138
135
        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)
 
136
        self.assertGDFO(graph, b'f', 2)
 
137
        self.assertGDFO(graph, b'e', 3)
 
138
        self.assertGDFO(graph, b'g', 1)
 
139
        self.assertGDFO(graph, b'b', 4)
 
140
        self.assertGDFO(graph, b'd', 4)
 
141
        self.assertGDFO(graph, b'a', 5)
 
142
        self.assertGDFO(graph, b'c', 5)
146
143
 
147
144
    def test_add_existing_node(self):
148
145
        graph = self.make_known_graph(test_graph.ancestry_1)
149
146
        # Add a node that already exists with identical content
150
147
        # This is a 'no-op'
151
 
        self.assertGDFO(graph, 'rev4', 5)
152
 
        graph.add_node('rev4', ['rev3', 'rev2b'])
153
 
        self.assertGDFO(graph, 'rev4', 5)
 
148
        self.assertGDFO(graph, b'rev4', 5)
 
149
        graph.add_node(b'rev4', [b'rev3', b'rev2b'])
 
150
        self.assertGDFO(graph, b'rev4', 5)
154
151
        # This also works if we use a tuple rather than a list
155
 
        graph.add_node('rev4', ('rev3', 'rev2b'))
 
152
        graph.add_node(b'rev4', (b'rev3', b'rev2b'))
156
153
 
157
154
    def test_add_existing_node_mismatched_parents(self):
158
155
        graph = self.make_known_graph(test_graph.ancestry_1)
159
 
        self.assertRaises(ValueError, graph.add_node, 'rev4',
160
 
                          ['rev2b', 'rev3'])
 
156
        self.assertRaises(ValueError, graph.add_node, b'rev4',
 
157
                          [b'rev2b', b'rev3'])
161
158
 
162
159
    def test_add_node_with_ghost_parent(self):
163
160
        graph = self.make_known_graph(test_graph.ancestry_1)
164
 
        graph.add_node('rev5', ['rev2b', 'revGhost'])
165
 
        self.assertGDFO(graph, 'rev5', 4)
166
 
        self.assertGDFO(graph, 'revGhost', 1)
 
161
        graph.add_node(b'rev5', [b'rev2b', b'revGhost'])
 
162
        self.assertGDFO(graph, b'rev5', 4)
 
163
        self.assertGDFO(graph, b'revGhost', 1)
167
164
 
168
165
    def test_add_new_root(self):
169
166
        graph = self.make_known_graph(test_graph.ancestry_1)
170
 
        graph.add_node('rev5', [])
171
 
        self.assertGDFO(graph, 'rev5', 1)
 
167
        graph.add_node(b'rev5', [])
 
168
        self.assertGDFO(graph, b'rev5', 1)
172
169
 
173
170
    def test_add_with_all_ghost_parents(self):
174
171
        graph = self.make_known_graph(test_graph.ancestry_1)
175
 
        graph.add_node('rev5', ['ghost'])
176
 
        self.assertGDFO(graph, 'rev5', 2)
177
 
        self.assertGDFO(graph, 'ghost', 1)
 
172
        graph.add_node(b'rev5', [b'ghost'])
 
173
        self.assertGDFO(graph, b'rev5', 2)
 
174
        self.assertGDFO(graph, b'ghost', 1)
178
175
 
179
176
    def test_gdfo_after_add_node(self):
180
177
        graph = self.make_known_graph(test_graph.ancestry_1)
181
 
        self.assertEqual([], graph.get_child_keys('rev4'))
182
 
        graph.add_node('rev5', ['rev4'])
183
 
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
184
 
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
185
 
        self.assertEqual([], graph.get_child_keys('rev5'))
186
 
        self.assertGDFO(graph, 'rev5', 6)
187
 
        graph.add_node('rev6', ['rev2b'])
188
 
        graph.add_node('rev7', ['rev6'])
189
 
        graph.add_node('rev8', ['rev7', 'rev5'])
190
 
        self.assertGDFO(graph, 'rev5', 6)
191
 
        self.assertGDFO(graph, 'rev6', 4)
192
 
        self.assertGDFO(graph, 'rev7', 5)
193
 
        self.assertGDFO(graph, 'rev8', 7)
 
178
        self.assertEqual([], graph.get_child_keys(b'rev4'))
 
179
        graph.add_node(b'rev5', [b'rev4'])
 
180
        self.assertEqual([b'rev4'], graph.get_parent_keys(b'rev5'))
 
181
        self.assertEqual([b'rev5'], graph.get_child_keys(b'rev4'))
 
182
        self.assertEqual([], graph.get_child_keys(b'rev5'))
 
183
        self.assertGDFO(graph, b'rev5', 6)
 
184
        graph.add_node(b'rev6', [b'rev2b'])
 
185
        graph.add_node(b'rev7', [b'rev6'])
 
186
        graph.add_node(b'rev8', [b'rev7', b'rev5'])
 
187
        self.assertGDFO(graph, b'rev5', 6)
 
188
        self.assertGDFO(graph, b'rev6', 4)
 
189
        self.assertGDFO(graph, b'rev7', 5)
 
190
        self.assertGDFO(graph, b'rev8', 7)
194
191
 
195
192
    def test_fill_in_ghost(self):
196
193
        graph = self.make_known_graph(test_graph.with_ghost)
197
194
        # Add in a couple nodes and then fill in the 'ghost' so that it should
198
195
        # cause renumbering of children nodes
199
 
        graph.add_node('x', [])
200
 
        graph.add_node('y', ['x'])
201
 
        graph.add_node('z', ['y'])
202
 
        graph.add_node('g', ['z'])
203
 
        self.assertGDFO(graph, 'f', 2)
204
 
        self.assertGDFO(graph, 'e', 3)
205
 
        self.assertGDFO(graph, 'x', 1)
206
 
        self.assertGDFO(graph, 'y', 2)
207
 
        self.assertGDFO(graph, 'z', 3)
208
 
        self.assertGDFO(graph, 'g', 4)
209
 
        self.assertGDFO(graph, 'b', 4)
210
 
        self.assertGDFO(graph, 'd', 5)
211
 
        self.assertGDFO(graph, 'a', 5)
212
 
        self.assertGDFO(graph, 'c', 6)
 
196
        graph.add_node(b'x', [])
 
197
        graph.add_node(b'y', [b'x'])
 
198
        graph.add_node(b'z', [b'y'])
 
199
        graph.add_node(b'g', [b'z'])
 
200
        self.assertGDFO(graph, b'f', 2)
 
201
        self.assertGDFO(graph, b'e', 3)
 
202
        self.assertGDFO(graph, b'x', 1)
 
203
        self.assertGDFO(graph, b'y', 2)
 
204
        self.assertGDFO(graph, b'z', 3)
 
205
        self.assertGDFO(graph, b'g', 4)
 
206
        self.assertGDFO(graph, b'b', 4)
 
207
        self.assertGDFO(graph, b'd', 5)
 
208
        self.assertGDFO(graph, b'a', 5)
 
209
        self.assertGDFO(graph, b'c', 6)
213
210
 
214
211
 
215
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
216
213
 
217
 
    do_cache = None # Set by load_tests
 
214
    scenarios = caching_scenarios() + non_caching_scenarios()
 
215
    do_cache = None  # Set by load_tests
218
216
 
219
217
    def test_heads_null(self):
220
218
        graph = self.make_known_graph(test_graph.ancestry_1)
221
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
222
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
223
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
224
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
225
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
219
        self.assertEqual({b'null:'}, graph.heads([b'null:']))
 
220
        self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
 
221
        self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
 
222
        self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
 
223
        self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
226
224
 
227
225
    def test_heads_one(self):
228
226
        # A single node will always be a head
229
227
        graph = self.make_known_graph(test_graph.ancestry_1)
230
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
231
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
232
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
233
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
234
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
235
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
228
        self.assertEqual({b'null:'}, graph.heads([b'null:']))
 
229
        self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
 
230
        self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
 
231
        self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
 
232
        self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
 
233
        self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
236
234
 
237
235
    def test_heads_single(self):
238
236
        graph = self.make_known_graph(test_graph.ancestry_1)
239
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
240
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
241
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
242
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
243
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
244
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
245
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
246
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
247
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
237
        self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
 
238
        self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
 
239
        self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
 
240
        self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
 
241
        self.assertEqual({b'rev3'}, graph.heads([b'rev3', b'rev2a']))
 
242
        self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
 
243
        self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
 
244
        self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
 
245
        self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
248
246
 
249
247
    def test_heads_two_heads(self):
250
248
        graph = self.make_known_graph(test_graph.ancestry_1)
251
 
        self.assertEqual(set(['rev2a', 'rev2b']),
252
 
                         graph.heads(['rev2a', 'rev2b']))
253
 
        self.assertEqual(set(['rev3', 'rev2b']),
254
 
                         graph.heads(['rev3', 'rev2b']))
 
249
        self.assertEqual({b'rev2a', b'rev2b'},
 
250
                         graph.heads([b'rev2a', b'rev2b']))
 
251
        self.assertEqual({b'rev3', b'rev2b'},
 
252
                         graph.heads([b'rev3', b'rev2b']))
255
253
 
256
254
    def test_heads_criss_cross(self):
257
255
        graph = self.make_known_graph(test_graph.criss_cross)
258
 
        self.assertEqual(set(['rev2a']),
259
 
                         graph.heads(['rev2a', 'rev1']))
260
 
        self.assertEqual(set(['rev2b']),
261
 
                         graph.heads(['rev2b', 'rev1']))
262
 
        self.assertEqual(set(['rev3a']),
263
 
                         graph.heads(['rev3a', 'rev1']))
264
 
        self.assertEqual(set(['rev3b']),
265
 
                         graph.heads(['rev3b', 'rev1']))
266
 
        self.assertEqual(set(['rev2a', 'rev2b']),
267
 
                         graph.heads(['rev2a', 'rev2b']))
268
 
        self.assertEqual(set(['rev3a']),
269
 
                         graph.heads(['rev3a', 'rev2a']))
270
 
        self.assertEqual(set(['rev3a']),
271
 
                         graph.heads(['rev3a', 'rev2b']))
272
 
        self.assertEqual(set(['rev3a']),
273
 
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
274
 
        self.assertEqual(set(['rev3b']),
275
 
                         graph.heads(['rev3b', 'rev2a']))
276
 
        self.assertEqual(set(['rev3b']),
277
 
                         graph.heads(['rev3b', 'rev2b']))
278
 
        self.assertEqual(set(['rev3b']),
279
 
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
280
 
        self.assertEqual(set(['rev3a', 'rev3b']),
281
 
                         graph.heads(['rev3a', 'rev3b']))
282
 
        self.assertEqual(set(['rev3a', 'rev3b']),
283
 
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
256
        self.assertEqual({b'rev2a'},
 
257
                         graph.heads([b'rev2a', b'rev1']))
 
258
        self.assertEqual({b'rev2b'},
 
259
                         graph.heads([b'rev2b', b'rev1']))
 
260
        self.assertEqual({b'rev3a'},
 
261
                         graph.heads([b'rev3a', b'rev1']))
 
262
        self.assertEqual({b'rev3b'},
 
263
                         graph.heads([b'rev3b', b'rev1']))
 
264
        self.assertEqual({b'rev2a', b'rev2b'},
 
265
                         graph.heads([b'rev2a', b'rev2b']))
 
266
        self.assertEqual({b'rev3a'},
 
267
                         graph.heads([b'rev3a', b'rev2a']))
 
268
        self.assertEqual({b'rev3a'},
 
269
                         graph.heads([b'rev3a', b'rev2b']))
 
270
        self.assertEqual({b'rev3a'},
 
271
                         graph.heads([b'rev3a', b'rev2a', b'rev2b']))
 
272
        self.assertEqual({b'rev3b'},
 
273
                         graph.heads([b'rev3b', b'rev2a']))
 
274
        self.assertEqual({b'rev3b'},
 
275
                         graph.heads([b'rev3b', b'rev2b']))
 
276
        self.assertEqual({b'rev3b'},
 
277
                         graph.heads([b'rev3b', b'rev2a', b'rev2b']))
 
278
        self.assertEqual({b'rev3a', b'rev3b'},
 
279
                         graph.heads([b'rev3a', b'rev3b']))
 
280
        self.assertEqual({b'rev3a', b'rev3b'},
 
281
                         graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
284
282
 
285
283
    def test_heads_shortcut(self):
286
284
        graph = self.make_known_graph(test_graph.history_shortcut)
287
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
288
 
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
289
 
        self.assertEqual(set(['rev3a', 'rev3b']),
290
 
                         graph.heads(['rev3a', 'rev3b']))
291
 
        self.assertEqual(set(['rev3a', 'rev3b']),
292
 
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
293
 
        self.assertEqual(set(['rev2a', 'rev3b']),
294
 
                         graph.heads(['rev2a', 'rev3b']))
295
 
        self.assertEqual(set(['rev2c', 'rev3a']),
296
 
                         graph.heads(['rev2c', 'rev3a']))
 
285
        self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
 
286
                         graph.heads([b'rev2a', b'rev2b', b'rev2c']))
 
287
        self.assertEqual({b'rev3a', b'rev3b'},
 
288
                         graph.heads([b'rev3a', b'rev3b']))
 
289
        self.assertEqual({b'rev3a', b'rev3b'},
 
290
                         graph.heads([b'rev2a', b'rev3a', b'rev3b']))
 
291
        self.assertEqual({b'rev2a', b'rev3b'},
 
292
                         graph.heads([b'rev2a', b'rev3b']))
 
293
        self.assertEqual({b'rev2c', b'rev3a'},
 
294
                         graph.heads([b'rev2c', b'rev3a']))
297
295
 
298
296
    def test_heads_linear(self):
299
297
        graph = self.make_known_graph(test_graph.racing_shortcuts)
300
 
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
301
 
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
302
 
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
303
 
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
298
        self.assertEqual({b'w'}, graph.heads([b'w', b's']))
 
299
        self.assertEqual({b'z'}, graph.heads([b'w', b's', b'z']))
 
300
        self.assertEqual({b'w', b'q'}, graph.heads([b'w', b's', b'q']))
 
301
        self.assertEqual({b'z'}, graph.heads([b's', b'z']))
304
302
 
305
303
    def test_heads_alt_merge(self):
306
304
        graph = self.make_known_graph(alt_merge)
307
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
 
305
        self.assertEqual({b'c'}, graph.heads([b'a', b'c']))
308
306
 
309
307
    def test_heads_with_ghost(self):
310
308
        graph = self.make_known_graph(test_graph.with_ghost)
311
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
312
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
313
 
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
314
 
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
315
 
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
316
 
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
317
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
318
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
 
309
        self.assertEqual({b'e', b'g'}, graph.heads([b'e', b'g']))
 
310
        self.assertEqual({b'a', b'c'}, graph.heads([b'a', b'c']))
 
311
        self.assertEqual({b'a', b'g'}, graph.heads([b'a', b'g']))
 
312
        self.assertEqual({b'f', b'g'}, graph.heads([b'f', b'g']))
 
313
        self.assertEqual({b'c'}, graph.heads([b'c', b'g']))
 
314
        self.assertEqual({b'c'}, graph.heads([b'c', b'b', b'd', b'g']))
 
315
        self.assertEqual({b'a', b'c'}, graph.heads([b'a', b'c', b'e', b'g']))
 
316
        self.assertEqual({b'a', b'c'}, graph.heads([b'a', b'c', b'f']))
319
317
 
320
318
    def test_filling_in_ghosts_resets_head_cache(self):
321
319
        graph = self.make_known_graph(test_graph.with_ghost)
322
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
320
        self.assertEqual({b'e', b'g'}, graph.heads([b'e', b'g']))
323
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
324
322
        # different
325
 
        graph.add_node('g', ['e'])
326
 
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
 
323
        graph.add_node(b'g', [b'e'])
 
324
        self.assertEqual({b'g'}, graph.heads([b'e', b'g']))
327
325
 
328
326
 
329
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
361
359
    def test_topo_sort_cycle(self):
362
360
        """TopoSort traps graph with cycles"""
363
361
        g = self.make_known_graph({0: [1],
364
 
                                  1: [0]})
 
362
                                   1: [0]})
365
363
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
366
364
 
367
365
    def test_topo_sort_cycle_2(self):
464
462
             'C': ['A', 'B']},
465
463
            'C',
466
464
            [('C', 0, (2,), False),
467
 
             ('B', 1, (1,1,1), True),
 
465
             ('B', 1, (1, 1, 1), True),
468
466
             ('A', 0, (1,), True),
469
467
             ],
470
468
            )
486
484
                 'F': ['B', 'D'],
487
485
                 }
488
486
        self.assertSortAndIterate(graph, 'F',
489
 
            [('F', 0, (3,), False),
490
 
             ('D', 1, (2,2,1), False),
491
 
             ('C', 2, (2,1,1), True),
492
 
             ('B', 0, (2,), False),
493
 
             ('A', 0, (1,), True),
494
 
             ])
 
487
                                  [('F', 0, (3,), False),
 
488
                                   ('D', 1, (2, 2, 1), False),
 
489
                                      ('C', 2, (2, 1, 1), True),
 
490
                                      ('B', 0, (2,), False),
 
491
                                      ('A', 0, (1,), True),
 
492
                                   ])
495
493
        # A
496
494
        # |
497
495
        # B-.
509
507
                 'F': ['B', 'D'],
510
508
                 }
511
509
        self.assertSortAndIterate(graph, 'F',
512
 
            [('F', 0, (3,), False),
513
 
             ('D', 1, (2,1,2), False),
514
 
             ('C', 2, (2,2,1), True),
515
 
             ('X', 1, (2,1,1), True),
516
 
             ('B', 0, (2,), False),
517
 
             ('A', 0, (1,), True),
518
 
             ])
 
510
                                  [('F', 0, (3,), False),
 
511
                                   ('D', 1, (2, 1, 2), False),
 
512
                                      ('C', 2, (2, 2, 1), True),
 
513
                                      ('X', 1, (2, 1, 1), True),
 
514
                                      ('B', 0, (2,), False),
 
515
                                      ('A', 0, (1,), True),
 
516
                                   ])
519
517
 
520
518
    def test_merge_depth_with_nested_merges(self):
521
519
        # the merge depth marker should reflect the depth of the revision
540
538
             'H': []
541
539
             },
542
540
            'A',
543
 
            [('A', 0, (3,),  False),
544
 
             ('B', 1, (1,3,2), False),
545
 
             ('C', 1, (1,3,1), True),
 
541
            [('A', 0, (3,), False),
 
542
             ('B', 1, (1, 3, 2), False),
 
543
             ('C', 1, (1, 3, 1), True),
546
544
             ('D', 0, (2,), False),
547
 
             ('E', 1, (1,1,2), False),
548
 
             ('F', 2, (1,2,1), True),
549
 
             ('G', 1, (1,1,1), True),
 
545
             ('E', 1, (1, 1, 2), False),
 
546
             ('F', 2, (1, 2, 1), True),
 
547
             ('G', 1, (1, 1, 1), True),
550
548
             ('H', 0, (1,), True),
551
549
             ],
552
550
            )
576
574
             'J': ['G', 'H'],
577
575
             'K': ['I'],
578
576
             'L': ['J', 'K'],
579
 
            },
 
577
             },
580
578
            'L',
581
579
            [('L', 0, (6,), False),
582
 
             ('K', 1, (1,3,2), False),
583
 
             ('I', 1, (1,3,1), True),
 
580
             ('K', 1, (1, 3, 2), False),
 
581
             ('I', 1, (1, 3, 1), True),
584
582
             ('J', 0, (5,), False),
585
 
             ('H', 1, (1,2,2), False),
586
 
             ('F', 1, (1,2,1), True),
 
583
             ('H', 1, (1, 2, 2), False),
 
584
             ('F', 1, (1, 2, 1), True),
587
585
             ('G', 0, (4,), False),
588
 
             ('E', 1, (1,1,2), False),
589
 
             ('C', 1, (1,1,1), True),
 
586
             ('E', 1, (1, 1, 2), False),
 
587
             ('C', 1, (1, 1, 1), True),
590
588
             ('D', 0, (3,), False),
591
589
             ('B', 0, (2,), False),
592
 
             ('A', 0, (1,),  True),
 
590
             ('A', 0, (1,), True),
593
591
             ],
594
592
            )
595
593
        # Adding a shortcut from the first revision should not change any of
609
607
             'L': ['J', 'K'],
610
608
             'M': ['A'],
611
609
             'N': ['L', 'M'],
612
 
            },
 
610
             },
613
611
            'N',
614
612
            [('N', 0, (7,), False),
615
 
             ('M', 1, (1,4,1), True),
 
613
             ('M', 1, (1, 4, 1), True),
616
614
             ('L', 0, (6,), False),
617
 
             ('K', 1, (1,3,2), False),
618
 
             ('I', 1, (1,3,1), True),
 
615
             ('K', 1, (1, 3, 2), False),
 
616
             ('I', 1, (1, 3, 1), True),
619
617
             ('J', 0, (5,), False),
620
 
             ('H', 1, (1,2,2), False),
621
 
             ('F', 1, (1,2,1), True),
 
618
             ('H', 1, (1, 2, 2), False),
 
619
             ('F', 1, (1, 2, 1), True),
622
620
             ('G', 0, (4,), False),
623
 
             ('E', 1, (1,1,2), False),
624
 
             ('C', 1, (1,1,1), True),
 
621
             ('E', 1, (1, 1, 2), False),
 
622
             ('C', 1, (1, 1, 1), True),
625
623
             ('D', 0, (3,), False),
626
624
             ('B', 0, (2,), False),
627
 
             ('A', 0, (1,),  True),
 
625
             ('A', 0, (1,), True),
628
626
             ],
629
627
            )
630
628
 
667
665
             },
668
666
            'A',
669
667
            [('A', 0, (2,), False),
670
 
             ('B', 1, (1,3,2), False),
671
 
             ('C', 2, (1,4,1), True),
672
 
             ('D', 1, (1,3,1), True),
673
 
             ('E', 1, (1,1,2), False),
674
 
             ('F', 2, (1,2,1), True),
675
 
             ('G', 1, (1,1,1), True),
 
668
             ('B', 1, (1, 3, 2), False),
 
669
             ('C', 2, (1, 4, 1), True),
 
670
             ('D', 1, (1, 3, 1), True),
 
671
             ('E', 1, (1, 1, 2), False),
 
672
             ('F', 2, (1, 2, 1), True),
 
673
             ('G', 1, (1, 1, 1), True),
676
674
             ('H', 0, (1,), True),
677
675
             ],
678
676
            )
685
683
             'C': ['A', 'B']},
686
684
            'C',
687
685
            [('C', 0, (2,), False),
688
 
             ('B', 1, (0,1,1), True),
 
686
             ('B', 1, (0, 1, 1), True),
689
687
             ('A', 0, (1,), True),
690
688
             ],
691
689
            )
711
709
        # root: A: []
712
710
        self.assertSortAndIterate(
713
711
            {'J': ['G', 'I'],
714
 
             'I': ['H',],
 
712
             'I': ['H', ],
715
713
             'H': ['A'],
716
714
             'G': ['D', 'F'],
717
715
             'F': ['E'],
723
721
             },
724
722
            'J',
725
723
            [('J', 0, (4,), False),
726
 
             ('I', 1, (1,3,2), False),
727
 
             ('H', 1, (1,3,1), True),
 
724
             ('I', 1, (1, 3, 2), False),
 
725
             ('H', 1, (1, 3, 1), True),
728
726
             ('G', 0, (3,), False),
729
 
             ('F', 1, (1,2,2), False),
730
 
             ('E', 1, (1,2,1), True),
 
727
             ('F', 1, (1, 2, 2), False),
 
728
             ('E', 1, (1, 2, 1), True),
731
729
             ('D', 0, (2,), False),
732
 
             ('C', 1, (1,1,2), False),
733
 
             ('B', 1, (1,1,1), True),
 
730
             ('C', 1, (1, 1, 2), False),
 
731
             ('B', 1, (1, 1, 1), True),
734
732
             ('A', 0, (1,), True),
735
733
             ],
736
734
            )
770
768
             'P': ['N'],
771
769
             'Q': ['O', 'P'],
772
770
             'R': ['J', 'Q'],
773
 
            },
 
771
             },
774
772
            'R',
775
773
            [('R', 0, (6,), False),
776
 
             ('Q', 1, (0,4,5), False),
777
 
             ('P', 2, (0,6,1), True),
778
 
             ('O', 1, (0,4,4), False),
779
 
             ('N', 1, (0,4,3), False),
780
 
             ('M', 2, (0,5,1), True),
781
 
             ('L', 1, (0,4,2), False),
782
 
             ('K', 1, (0,4,1), True),
 
774
             ('Q', 1, (0, 4, 5), False),
 
775
             ('P', 2, (0, 6, 1), True),
 
776
             ('O', 1, (0, 4, 4), False),
 
777
             ('N', 1, (0, 4, 3), False),
 
778
             ('M', 2, (0, 5, 1), True),
 
779
             ('L', 1, (0, 4, 2), False),
 
780
             ('K', 1, (0, 4, 1), True),
783
781
             ('J', 0, (5,), False),
784
 
             ('I', 1, (0,3,1), True),
 
782
             ('I', 1, (0, 3, 1), True),
785
783
             ('H', 0, (4,), False),
786
 
             ('G', 1, (0,1,3), False),
787
 
             ('F', 2, (0,2,1), True),
788
 
             ('E', 1, (0,1,2), False),
789
 
             ('D', 1, (0,1,1), True),
 
784
             ('G', 1, (0, 1, 3), False),
 
785
             ('F', 2, (0, 2, 1), True),
 
786
             ('E', 1, (0, 1, 2), False),
 
787
             ('D', 1, (0, 1, 1), True),
790
788
             ('C', 0, (3,), False),
791
789
             ('B', 0, (2,), False),
792
790
             ('A', 0, (1,), True),
804
802
            {'A': [],
805
803
             'B': ['A'],
806
804
             'C': ['B', 'ghost'],
807
 
            },
 
805
             },
808
806
            'C',
809
807
            [('C', 0, (3,), False),
810
808
             ('B', 0, (2,), False),
811
809
             ('A', 0, (1,), True),
812
 
            ])
 
810
             ])
813
811
 
814
812
    def test_lefthand_ghost(self):
815
813
        # ghost
820
818
        self.assertSortAndIterate(
821
819
            {'A': ['ghost'],
822
820
             'B': ['A'],
823
 
            }, 'B',
 
821
             }, 'B',
824
822
            [('B', 0, (2,), False),
825
823
             ('A', 0, (1,), True),
826
 
            ])
 
824
             ])
827
825
 
828
826
    def test_graph_cycle(self):
829
827
        # merge_sort should fail with a simple error when a graph cycle is
839
837
        # |'-'
840
838
        # E
841
839
        self.assertRaises(errors.GraphCycleError,
842
 
            self.assertSortAndIterate,
843
 
                {'A': [],
844
 
                 'B': ['D'],
845
 
                 'C': ['B'],
846
 
                 'D': ['C'],
847
 
                 'E': ['D'],
848
 
                },
849
 
                'E',
850
 
                [])
 
840
                          self.assertSortAndIterate,
 
841
                          {'A': [],
 
842
                           'B': ['D'],
 
843
                              'C': ['B'],
 
844
                              'D': ['C'],
 
845
                              'E': ['D'],
 
846
                           },
 
847
                          'E',
 
848
                          [])
851
849
 
852
850
 
853
851
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
864
862
        self.assertSorted([], {})
865
863
 
866
864
    def test_single(self):
867
 
        self.assertSorted(['a'], {'a':()})
868
 
        self.assertSorted([('a',)], {('a',):()})
869
 
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
865
        self.assertSorted(['a'], {'a': ()})
 
866
        self.assertSorted([('a',)], {('a',): ()})
 
867
        self.assertSorted([('F', 'a')], {('F', 'a'): ()})
870
868
 
871
869
    def test_linear(self):
872
 
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
870
        self.assertSorted(['c', 'b', 'a'], {'a': (), 'b': ('a',), 'c': ('b',)})
873
871
        self.assertSorted([('c',), ('b',), ('a',)],
874
 
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
872
                          {('a',): (), ('b',): (('a',),), ('c',): (('b',),)})
875
873
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
876
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
874
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
877
875
                           ('F', 'c'): (('F', 'b'),)})
878
876
 
879
877
    def test_mixed_ancestries(self):
881
879
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
882
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
883
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
884
 
                          ],
885
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
882
                           ],
 
883
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
886
884
                           ('F', 'c'): (('F', 'b'),),
887
 
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
885
                           ('G', 'a'): (), ('G', 'b'): (('G', 'a'),),
888
886
                           ('G', 'c'): (('G', 'b'),),
889
 
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
887
                           ('Q', 'a'): (), ('Q', 'b'): (('Q', 'a'),),
890
888
                           ('Q', 'c'): (('Q', 'b'),),
891
 
                          })
 
889
                           })
892
890
 
893
891
    def test_stable_sorting(self):
894
892
        # the sort order should be stable even when extra nodes are added
895
893
        self.assertSorted(['b', 'c', 'a'],
896
 
                          {'a':(), 'b':('a',), 'c':('a',)})
897
 
        self.assertSorted(['b', 'c', 'd', 'a'],
898
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
899
 
        self.assertSorted(['b', 'c', 'd', 'a'],
900
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('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',)})
901
899
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
902
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
903
 
                           'Z':('a',)})
 
900
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
 
901
                           'Z': ('a',)})
904
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
905
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
906
 
                           'Z':('a',),
907
 
                           'e':('b', 'c', 'd'),
908
 
                           'f':('d', 'Z'),
 
903
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
 
904
                           'Z': ('a',),
 
905
                           'e': ('b', 'c', 'd'),
 
906
                           'f': ('d', 'Z'),
909
907
                           })
910
908
 
911
909
    def test_skip_ghost(self):
912
910
        self.assertSorted(['b', 'c', 'a'],
913
 
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
911
                          {'a': (), 'b': ('a', 'ghost'), 'c': ('a',)})
914
912
 
915
913
    def test_skip_mainline_ghost(self):
916
914
        self.assertSorted(['b', 'c', 'a'],
917
 
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})
 
915
                          {'a': (), 'b': ('ghost', 'a'), 'c': ('a',)})