/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: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
1
 
# Copyright (C) 2009, 2010, 2011 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 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 .. import (
 
21
from bzrlib import (
22
22
    errors,
 
23
    graph as _mod_graph,
23
24
    _known_graph_py,
24
25
    tests,
25
26
    )
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():
 
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."""
35
33
    scenarios = [
36
34
        ('python', {'module': _known_graph_py, 'do_cache': True}),
37
35
    ]
 
36
    caching_scenarios = [
 
37
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
38
    ]
 
39
    suite = loader.suiteClass()
38
40
    if compiled_known_graph_feature.available():
39
41
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
40
42
                                'do_cache': True}))
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(
 
43
        caching_scenarios.append(
50
44
            ('C-nocache', {'module': compiled_known_graph_feature.module,
51
45
                           'do_cache': False}))
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')
 
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')
60
64
 
61
65
 
62
66
#  a
66
70
#  c |
67
71
#   \|
68
72
#    d
69
 
alt_merge = {b'a': [], b'b': [b'a'], b'c': [b'b'], b'd': [b'a', b'c']}
 
73
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
70
74
 
71
75
 
72
76
class TestCaseWithKnownGraph(tests.TestCase):
73
77
 
74
 
    scenarios = caching_scenarios()
75
 
    module = None  # Set by load_tests
 
78
    module = None # Set by load_tests
76
79
 
77
80
    def make_known_graph(self, ancestry):
78
81
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
86
89
 
87
90
    def test_children_ancestry1(self):
88
91
        graph = self.make_known_graph(test_graph.ancestry_1)
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')
 
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')
96
99
 
97
100
    def test_parent_ancestry1(self):
98
101
        graph = self.make_known_graph(test_graph.ancestry_1)
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
 
 
 
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
    
107
110
    def test_parent_with_ghost(self):
108
111
        graph = self.make_known_graph(test_graph.with_ghost)
109
 
        self.assertEqual(None, graph.get_parent_keys(b'g'))
 
112
        self.assertEqual(None, graph.get_parent_keys('g'))
110
113
 
111
114
    def test_gdfo_ancestry_1(self):
112
115
        graph = self.make_known_graph(test_graph.ancestry_1)
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)
 
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)
118
121
 
119
122
    def test_gdfo_feature_branch(self):
120
123
        graph = self.make_known_graph(test_graph.feature_branch)
121
 
        self.assertGDFO(graph, b'rev1', 2)
122
 
        self.assertGDFO(graph, b'rev2b', 3)
123
 
        self.assertGDFO(graph, b'rev3b', 4)
 
124
        self.assertGDFO(graph, 'rev1', 2)
 
125
        self.assertGDFO(graph, 'rev2b', 3)
 
126
        self.assertGDFO(graph, 'rev3b', 4)
124
127
 
125
128
    def test_gdfo_extended_history_shortcut(self):
126
129
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
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)
 
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)
133
136
 
134
137
    def test_gdfo_with_ghost(self):
135
138
        graph = self.make_known_graph(test_graph.with_ghost)
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)
 
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)
143
146
 
144
147
    def test_add_existing_node(self):
145
148
        graph = self.make_known_graph(test_graph.ancestry_1)
146
149
        # Add a node that already exists with identical content
147
150
        # This is a 'no-op'
148
 
        self.assertGDFO(graph, b'rev4', 5)
149
 
        graph.add_node(b'rev4', [b'rev3', b'rev2b'])
150
 
        self.assertGDFO(graph, b'rev4', 5)
 
151
        self.assertGDFO(graph, 'rev4', 5)
 
152
        graph.add_node('rev4', ['rev3', 'rev2b'])
 
153
        self.assertGDFO(graph, 'rev4', 5)
151
154
        # This also works if we use a tuple rather than a list
152
 
        graph.add_node(b'rev4', (b'rev3', b'rev2b'))
 
155
        graph.add_node('rev4', ('rev3', 'rev2b'))
153
156
 
154
157
    def test_add_existing_node_mismatched_parents(self):
155
158
        graph = self.make_known_graph(test_graph.ancestry_1)
156
 
        self.assertRaises(ValueError, graph.add_node, b'rev4',
157
 
                          [b'rev2b', b'rev3'])
 
159
        self.assertRaises(ValueError, graph.add_node, 'rev4',
 
160
                          ['rev2b', 'rev3'])
158
161
 
159
162
    def test_add_node_with_ghost_parent(self):
160
163
        graph = self.make_known_graph(test_graph.ancestry_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)
 
164
        graph.add_node('rev5', ['rev2b', 'revGhost'])
 
165
        self.assertGDFO(graph, 'rev5', 4)
 
166
        self.assertGDFO(graph, 'revGhost', 1)
164
167
 
165
168
    def test_add_new_root(self):
166
169
        graph = self.make_known_graph(test_graph.ancestry_1)
167
 
        graph.add_node(b'rev5', [])
168
 
        self.assertGDFO(graph, b'rev5', 1)
 
170
        graph.add_node('rev5', [])
 
171
        self.assertGDFO(graph, 'rev5', 1)
169
172
 
170
173
    def test_add_with_all_ghost_parents(self):
171
174
        graph = self.make_known_graph(test_graph.ancestry_1)
172
 
        graph.add_node(b'rev5', [b'ghost'])
173
 
        self.assertGDFO(graph, b'rev5', 2)
174
 
        self.assertGDFO(graph, b'ghost', 1)
 
175
        graph.add_node('rev5', ['ghost'])
 
176
        self.assertGDFO(graph, 'rev5', 2)
 
177
        self.assertGDFO(graph, 'ghost', 1)
175
178
 
176
179
    def test_gdfo_after_add_node(self):
177
180
        graph = self.make_known_graph(test_graph.ancestry_1)
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)
 
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)
191
194
 
192
195
    def test_fill_in_ghost(self):
193
196
        graph = self.make_known_graph(test_graph.with_ghost)
194
197
        # Add in a couple nodes and then fill in the 'ghost' so that it should
195
198
        # cause renumbering of children nodes
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)
 
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)
210
213
 
211
214
 
212
215
class TestKnownGraphHeads(TestCaseWithKnownGraph):
213
216
 
214
 
    scenarios = caching_scenarios() + non_caching_scenarios()
215
 
    do_cache = None  # Set by load_tests
 
217
    do_cache = None # Set by load_tests
216
218
 
217
219
    def test_heads_null(self):
218
220
        graph = self.make_known_graph(test_graph.ancestry_1)
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:')))
 
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:')))
224
226
 
225
227
    def test_heads_one(self):
226
228
        # A single node will always be a head
227
229
        graph = self.make_known_graph(test_graph.ancestry_1)
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']))
 
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']))
234
236
 
235
237
    def test_heads_single(self):
236
238
        graph = self.make_known_graph(test_graph.ancestry_1)
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']))
 
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']))
246
248
 
247
249
    def test_heads_two_heads(self):
248
250
        graph = self.make_known_graph(test_graph.ancestry_1)
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']))
 
251
        self.assertEqual(set(['rev2a', 'rev2b']),
 
252
                         graph.heads(['rev2a', 'rev2b']))
 
253
        self.assertEqual(set(['rev3', 'rev2b']),
 
254
                         graph.heads(['rev3', 'rev2b']))
253
255
 
254
256
    def test_heads_criss_cross(self):
255
257
        graph = self.make_known_graph(test_graph.criss_cross)
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']))
 
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']))
282
284
 
283
285
    def test_heads_shortcut(self):
284
286
        graph = self.make_known_graph(test_graph.history_shortcut)
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']))
 
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']))
295
297
 
296
298
    def test_heads_linear(self):
297
299
        graph = self.make_known_graph(test_graph.racing_shortcuts)
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']))
 
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']))
302
304
 
303
305
    def test_heads_alt_merge(self):
304
306
        graph = self.make_known_graph(alt_merge)
305
 
        self.assertEqual({b'c'}, graph.heads([b'a', b'c']))
 
307
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
306
308
 
307
309
    def test_heads_with_ghost(self):
308
310
        graph = self.make_known_graph(test_graph.with_ghost)
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']))
 
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']))
317
319
 
318
320
    def test_filling_in_ghosts_resets_head_cache(self):
319
321
        graph = self.make_known_graph(test_graph.with_ghost)
320
 
        self.assertEqual({b'e', b'g'}, graph.heads([b'e', b'g']))
 
322
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
321
323
        # 'g' is filled in, and decends from 'e', so the heads result is now
322
324
        # different
323
 
        graph.add_node(b'g', [b'e'])
324
 
        self.assertEqual({b'g'}, graph.heads([b'e', b'g']))
 
325
        graph.add_node('g', ['e'])
 
326
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
325
327
 
326
328
 
327
329
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
359
361
    def test_topo_sort_cycle(self):
360
362
        """TopoSort traps graph with cycles"""
361
363
        g = self.make_known_graph({0: [1],
362
 
                                   1: [0]})
 
364
                                  1: [0]})
363
365
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
364
366
 
365
367
    def test_topo_sort_cycle_2(self):
462
464
             'C': ['A', 'B']},
463
465
            'C',
464
466
            [('C', 0, (2,), False),
465
 
             ('B', 1, (1, 1, 1), True),
 
467
             ('B', 1, (1,1,1), True),
466
468
             ('A', 0, (1,), True),
467
469
             ],
468
470
            )
484
486
                 'F': ['B', 'D'],
485
487
                 }
486
488
        self.assertSortAndIterate(graph, 'F',
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
 
                                   ])
 
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
             ])
493
495
        # A
494
496
        # |
495
497
        # B-.
507
509
                 'F': ['B', 'D'],
508
510
                 }
509
511
        self.assertSortAndIterate(graph, 'F',
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
 
                                   ])
 
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
             ])
517
519
 
518
520
    def test_merge_depth_with_nested_merges(self):
519
521
        # the merge depth marker should reflect the depth of the revision
538
540
             'H': []
539
541
             },
540
542
            'A',
541
 
            [('A', 0, (3,), False),
542
 
             ('B', 1, (1, 3, 2), False),
543
 
             ('C', 1, (1, 3, 1), True),
 
543
            [('A', 0, (3,),  False),
 
544
             ('B', 1, (1,3,2), False),
 
545
             ('C', 1, (1,3,1), True),
544
546
             ('D', 0, (2,), False),
545
 
             ('E', 1, (1, 1, 2), False),
546
 
             ('F', 2, (1, 2, 1), True),
547
 
             ('G', 1, (1, 1, 1), True),
 
547
             ('E', 1, (1,1,2), False),
 
548
             ('F', 2, (1,2,1), True),
 
549
             ('G', 1, (1,1,1), True),
548
550
             ('H', 0, (1,), True),
549
551
             ],
550
552
            )
574
576
             'J': ['G', 'H'],
575
577
             'K': ['I'],
576
578
             'L': ['J', 'K'],
577
 
             },
 
579
            },
578
580
            'L',
579
581
            [('L', 0, (6,), False),
580
 
             ('K', 1, (1, 3, 2), False),
581
 
             ('I', 1, (1, 3, 1), True),
 
582
             ('K', 1, (1,3,2), False),
 
583
             ('I', 1, (1,3,1), True),
582
584
             ('J', 0, (5,), False),
583
 
             ('H', 1, (1, 2, 2), False),
584
 
             ('F', 1, (1, 2, 1), True),
 
585
             ('H', 1, (1,2,2), False),
 
586
             ('F', 1, (1,2,1), True),
585
587
             ('G', 0, (4,), False),
586
 
             ('E', 1, (1, 1, 2), False),
587
 
             ('C', 1, (1, 1, 1), True),
 
588
             ('E', 1, (1,1,2), False),
 
589
             ('C', 1, (1,1,1), True),
588
590
             ('D', 0, (3,), False),
589
591
             ('B', 0, (2,), False),
590
 
             ('A', 0, (1,), True),
 
592
             ('A', 0, (1,),  True),
591
593
             ],
592
594
            )
593
595
        # Adding a shortcut from the first revision should not change any of
607
609
             'L': ['J', 'K'],
608
610
             'M': ['A'],
609
611
             'N': ['L', 'M'],
610
 
             },
 
612
            },
611
613
            'N',
612
614
            [('N', 0, (7,), False),
613
 
             ('M', 1, (1, 4, 1), True),
 
615
             ('M', 1, (1,4,1), True),
614
616
             ('L', 0, (6,), False),
615
 
             ('K', 1, (1, 3, 2), False),
616
 
             ('I', 1, (1, 3, 1), True),
 
617
             ('K', 1, (1,3,2), False),
 
618
             ('I', 1, (1,3,1), True),
617
619
             ('J', 0, (5,), False),
618
 
             ('H', 1, (1, 2, 2), False),
619
 
             ('F', 1, (1, 2, 1), True),
 
620
             ('H', 1, (1,2,2), False),
 
621
             ('F', 1, (1,2,1), True),
620
622
             ('G', 0, (4,), False),
621
 
             ('E', 1, (1, 1, 2), False),
622
 
             ('C', 1, (1, 1, 1), True),
 
623
             ('E', 1, (1,1,2), False),
 
624
             ('C', 1, (1,1,1), True),
623
625
             ('D', 0, (3,), False),
624
626
             ('B', 0, (2,), False),
625
 
             ('A', 0, (1,), True),
 
627
             ('A', 0, (1,),  True),
626
628
             ],
627
629
            )
628
630
 
665
667
             },
666
668
            'A',
667
669
            [('A', 0, (2,), False),
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),
 
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),
674
676
             ('H', 0, (1,), True),
675
677
             ],
676
678
            )
683
685
             'C': ['A', 'B']},
684
686
            'C',
685
687
            [('C', 0, (2,), False),
686
 
             ('B', 1, (0, 1, 1), True),
 
688
             ('B', 1, (0,1,1), True),
687
689
             ('A', 0, (1,), True),
688
690
             ],
689
691
            )
709
711
        # root: A: []
710
712
        self.assertSortAndIterate(
711
713
            {'J': ['G', 'I'],
712
 
             'I': ['H', ],
 
714
             'I': ['H',],
713
715
             'H': ['A'],
714
716
             'G': ['D', 'F'],
715
717
             'F': ['E'],
721
723
             },
722
724
            'J',
723
725
            [('J', 0, (4,), False),
724
 
             ('I', 1, (1, 3, 2), False),
725
 
             ('H', 1, (1, 3, 1), True),
 
726
             ('I', 1, (1,3,2), False),
 
727
             ('H', 1, (1,3,1), True),
726
728
             ('G', 0, (3,), False),
727
 
             ('F', 1, (1, 2, 2), False),
728
 
             ('E', 1, (1, 2, 1), True),
 
729
             ('F', 1, (1,2,2), False),
 
730
             ('E', 1, (1,2,1), True),
729
731
             ('D', 0, (2,), False),
730
 
             ('C', 1, (1, 1, 2), False),
731
 
             ('B', 1, (1, 1, 1), True),
 
732
             ('C', 1, (1,1,2), False),
 
733
             ('B', 1, (1,1,1), True),
732
734
             ('A', 0, (1,), True),
733
735
             ],
734
736
            )
768
770
             'P': ['N'],
769
771
             'Q': ['O', 'P'],
770
772
             'R': ['J', 'Q'],
771
 
             },
 
773
            },
772
774
            'R',
773
775
            [('R', 0, (6,), False),
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),
 
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),
781
783
             ('J', 0, (5,), False),
782
 
             ('I', 1, (0, 3, 1), True),
 
784
             ('I', 1, (0,3,1), True),
783
785
             ('H', 0, (4,), False),
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),
 
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),
788
790
             ('C', 0, (3,), False),
789
791
             ('B', 0, (2,), False),
790
792
             ('A', 0, (1,), True),
802
804
            {'A': [],
803
805
             'B': ['A'],
804
806
             'C': ['B', 'ghost'],
805
 
             },
 
807
            },
806
808
            'C',
807
809
            [('C', 0, (3,), False),
808
810
             ('B', 0, (2,), False),
809
811
             ('A', 0, (1,), True),
810
 
             ])
 
812
            ])
811
813
 
812
814
    def test_lefthand_ghost(self):
813
815
        # ghost
818
820
        self.assertSortAndIterate(
819
821
            {'A': ['ghost'],
820
822
             'B': ['A'],
821
 
             }, 'B',
 
823
            }, 'B',
822
824
            [('B', 0, (2,), False),
823
825
             ('A', 0, (1,), True),
824
 
             ])
 
826
            ])
825
827
 
826
828
    def test_graph_cycle(self):
827
829
        # merge_sort should fail with a simple error when a graph cycle is
837
839
        # |'-'
838
840
        # E
839
841
        self.assertRaises(errors.GraphCycleError,
840
 
                          self.assertSortAndIterate,
841
 
                          {'A': [],
842
 
                           'B': ['D'],
843
 
                              'C': ['B'],
844
 
                              'D': ['C'],
845
 
                              'E': ['D'],
846
 
                           },
847
 
                          'E',
848
 
                          [])
 
842
            self.assertSortAndIterate,
 
843
                {'A': [],
 
844
                 'B': ['D'],
 
845
                 'C': ['B'],
 
846
                 'D': ['C'],
 
847
                 'E': ['D'],
 
848
                },
 
849
                'E',
 
850
                [])
849
851
 
850
852
 
851
853
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
862
864
        self.assertSorted([], {})
863
865
 
864
866
    def test_single(self):
865
 
        self.assertSorted(['a'], {'a': ()})
866
 
        self.assertSorted([('a',)], {('a',): ()})
867
 
        self.assertSorted([('F', 'a')], {('F', 'a'): ()})
 
867
        self.assertSorted(['a'], {'a':()})
 
868
        self.assertSorted([('a',)], {('a',):()})
 
869
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
868
870
 
869
871
    def test_linear(self):
870
 
        self.assertSorted(['c', 'b', 'a'], {'a': (), 'b': ('a',), 'c': ('b',)})
 
872
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
871
873
        self.assertSorted([('c',), ('b',), ('a',)],
872
 
                          {('a',): (), ('b',): (('a',),), ('c',): (('b',),)})
 
874
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
873
875
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
874
 
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
 
876
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
875
877
                           ('F', 'c'): (('F', 'b'),)})
876
878
 
877
879
    def test_mixed_ancestries(self):
879
881
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
880
882
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
881
883
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
882
 
                           ],
883
 
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
 
884
                          ],
 
885
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
884
886
                           ('F', 'c'): (('F', 'b'),),
885
 
                           ('G', 'a'): (), ('G', 'b'): (('G', 'a'),),
 
887
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
886
888
                           ('G', 'c'): (('G', 'b'),),
887
 
                           ('Q', 'a'): (), ('Q', 'b'): (('Q', 'a'),),
 
889
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
888
890
                           ('Q', 'c'): (('Q', 'b'),),
889
 
                           })
 
891
                          })
890
892
 
891
893
    def test_stable_sorting(self):
892
894
        # the sort order should be stable even when extra nodes are added
893
895
        self.assertSorted(['b', 'c', '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',)})
 
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',)})
899
901
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
900
 
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
901
 
                           'Z': ('a',)})
 
902
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
903
                           'Z':('a',)})
902
904
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
903
 
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
904
 
                           'Z': ('a',),
905
 
                           'e': ('b', 'c', 'd'),
906
 
                           'f': ('d', 'Z'),
 
905
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
906
                           'Z':('a',),
 
907
                           'e':('b', 'c', 'd'),
 
908
                           'f':('d', 'Z'),
907
909
                           })
908
910
 
909
911
    def test_skip_ghost(self):
910
912
        self.assertSorted(['b', 'c', 'a'],
911
 
                          {'a': (), 'b': ('a', 'ghost'), 'c': ('a',)})
 
913
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
912
914
 
913
915
    def test_skip_mainline_ghost(self):
914
916
        self.assertSorted(['b', 'c', 'a'],
915
 
                          {'a': (), 'b': ('ghost', 'a'), 'c': ('a',)})
 
917
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})