/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: 2018-02-18 21:42:57 UTC
  • mto: This revision was merged to the branch mainline in revision 6859.
  • Revision ID: jelmer@jelmer.uk-20180218214257-jpevutp1wa30tz3v
Update TODO to reference Breezy, not Bazaar.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test__known_graph.py
66
66
#  c |
67
67
#   \|
68
68
#    d
69
 
alt_merge = {b'a': [], b'b': [b'a'], b'c': [b'b'], b'd': [b'a', b'c']}
 
69
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
70
70
 
71
71
 
72
72
class TestCaseWithKnownGraph(tests.TestCase):
73
73
 
74
74
    scenarios = caching_scenarios()
75
 
    module = None  # Set by load_tests
 
75
    module = None # Set by load_tests
76
76
 
77
77
    def make_known_graph(self, ancestry):
78
78
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
86
86
 
87
87
    def test_children_ancestry1(self):
88
88
        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')
 
89
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
 
90
        self.assertEqual(['rev2a', 'rev2b'],
 
91
                         sorted(graph.get_child_keys('rev1')))
 
92
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
 
93
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
 
94
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
 
95
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
96
96
 
97
97
    def test_parent_ancestry1(self):
98
98
        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
 
 
 
99
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
 
100
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
 
101
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
 
102
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
 
103
        self.assertEqual(['rev2b', 'rev3'],
 
104
                         sorted(graph.get_parent_keys('rev4')))
 
105
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
106
    
107
107
    def test_parent_with_ghost(self):
108
108
        graph = self.make_known_graph(test_graph.with_ghost)
109
 
        self.assertEqual(None, graph.get_parent_keys(b'g'))
 
109
        self.assertEqual(None, graph.get_parent_keys('g'))
110
110
 
111
111
    def test_gdfo_ancestry_1(self):
112
112
        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)
 
113
        self.assertGDFO(graph, 'rev1', 2)
 
114
        self.assertGDFO(graph, 'rev2b', 3)
 
115
        self.assertGDFO(graph, 'rev2a', 3)
 
116
        self.assertGDFO(graph, 'rev3', 4)
 
117
        self.assertGDFO(graph, 'rev4', 5)
118
118
 
119
119
    def test_gdfo_feature_branch(self):
120
120
        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)
 
121
        self.assertGDFO(graph, 'rev1', 2)
 
122
        self.assertGDFO(graph, 'rev2b', 3)
 
123
        self.assertGDFO(graph, 'rev3b', 4)
124
124
 
125
125
    def test_gdfo_extended_history_shortcut(self):
126
126
        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)
 
127
        self.assertGDFO(graph, 'a', 2)
 
128
        self.assertGDFO(graph, 'b', 3)
 
129
        self.assertGDFO(graph, 'c', 4)
 
130
        self.assertGDFO(graph, 'd', 5)
 
131
        self.assertGDFO(graph, 'e', 6)
 
132
        self.assertGDFO(graph, 'f', 6)
133
133
 
134
134
    def test_gdfo_with_ghost(self):
135
135
        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)
 
136
        self.assertGDFO(graph, 'f', 2)
 
137
        self.assertGDFO(graph, 'e', 3)
 
138
        self.assertGDFO(graph, 'g', 1)
 
139
        self.assertGDFO(graph, 'b', 4)
 
140
        self.assertGDFO(graph, 'd', 4)
 
141
        self.assertGDFO(graph, 'a', 5)
 
142
        self.assertGDFO(graph, 'c', 5)
143
143
 
144
144
    def test_add_existing_node(self):
145
145
        graph = self.make_known_graph(test_graph.ancestry_1)
146
146
        # Add a node that already exists with identical content
147
147
        # 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)
 
148
        self.assertGDFO(graph, 'rev4', 5)
 
149
        graph.add_node('rev4', ['rev3', 'rev2b'])
 
150
        self.assertGDFO(graph, 'rev4', 5)
151
151
        # This also works if we use a tuple rather than a list
152
 
        graph.add_node(b'rev4', (b'rev3', b'rev2b'))
 
152
        graph.add_node('rev4', ('rev3', 'rev2b'))
153
153
 
154
154
    def test_add_existing_node_mismatched_parents(self):
155
155
        graph = self.make_known_graph(test_graph.ancestry_1)
156
 
        self.assertRaises(ValueError, graph.add_node, b'rev4',
157
 
                          [b'rev2b', b'rev3'])
 
156
        self.assertRaises(ValueError, graph.add_node, 'rev4',
 
157
                          ['rev2b', 'rev3'])
158
158
 
159
159
    def test_add_node_with_ghost_parent(self):
160
160
        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)
 
161
        graph.add_node('rev5', ['rev2b', 'revGhost'])
 
162
        self.assertGDFO(graph, 'rev5', 4)
 
163
        self.assertGDFO(graph, 'revGhost', 1)
164
164
 
165
165
    def test_add_new_root(self):
166
166
        graph = self.make_known_graph(test_graph.ancestry_1)
167
 
        graph.add_node(b'rev5', [])
168
 
        self.assertGDFO(graph, b'rev5', 1)
 
167
        graph.add_node('rev5', [])
 
168
        self.assertGDFO(graph, 'rev5', 1)
169
169
 
170
170
    def test_add_with_all_ghost_parents(self):
171
171
        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)
 
172
        graph.add_node('rev5', ['ghost'])
 
173
        self.assertGDFO(graph, 'rev5', 2)
 
174
        self.assertGDFO(graph, 'ghost', 1)
175
175
 
176
176
    def test_gdfo_after_add_node(self):
177
177
        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)
 
178
        self.assertEqual([], graph.get_child_keys('rev4'))
 
179
        graph.add_node('rev5', ['rev4'])
 
180
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
 
181
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
 
182
        self.assertEqual([], graph.get_child_keys('rev5'))
 
183
        self.assertGDFO(graph, 'rev5', 6)
 
184
        graph.add_node('rev6', ['rev2b'])
 
185
        graph.add_node('rev7', ['rev6'])
 
186
        graph.add_node('rev8', ['rev7', 'rev5'])
 
187
        self.assertGDFO(graph, 'rev5', 6)
 
188
        self.assertGDFO(graph, 'rev6', 4)
 
189
        self.assertGDFO(graph, 'rev7', 5)
 
190
        self.assertGDFO(graph, 'rev8', 7)
191
191
 
192
192
    def test_fill_in_ghost(self):
193
193
        graph = self.make_known_graph(test_graph.with_ghost)
194
194
        # Add in a couple nodes and then fill in the 'ghost' so that it should
195
195
        # 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)
 
196
        graph.add_node('x', [])
 
197
        graph.add_node('y', ['x'])
 
198
        graph.add_node('z', ['y'])
 
199
        graph.add_node('g', ['z'])
 
200
        self.assertGDFO(graph, 'f', 2)
 
201
        self.assertGDFO(graph, 'e', 3)
 
202
        self.assertGDFO(graph, 'x', 1)
 
203
        self.assertGDFO(graph, 'y', 2)
 
204
        self.assertGDFO(graph, 'z', 3)
 
205
        self.assertGDFO(graph, 'g', 4)
 
206
        self.assertGDFO(graph, 'b', 4)
 
207
        self.assertGDFO(graph, 'd', 5)
 
208
        self.assertGDFO(graph, 'a', 5)
 
209
        self.assertGDFO(graph, 'c', 6)
210
210
 
211
211
 
212
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
213
213
 
214
214
    scenarios = caching_scenarios() + non_caching_scenarios()
215
 
    do_cache = None  # Set by load_tests
 
215
    do_cache = None # Set by load_tests
216
216
 
217
217
    def test_heads_null(self):
218
218
        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:')))
 
219
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
220
        self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
 
221
        self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
 
222
        self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
 
223
        self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
224
224
 
225
225
    def test_heads_one(self):
226
226
        # A single node will always be a head
227
227
        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']))
 
228
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
229
        self.assertEqual({'rev1'}, graph.heads(['rev1']))
 
230
        self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
 
231
        self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
 
232
        self.assertEqual({'rev3'}, graph.heads(['rev3']))
 
233
        self.assertEqual({'rev4'}, graph.heads(['rev4']))
234
234
 
235
235
    def test_heads_single(self):
236
236
        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']))
 
237
        self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
 
238
        self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
 
239
        self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
 
240
        self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
 
241
        self.assertEqual({'rev3'}, graph.heads(['rev3', 'rev2a']))
 
242
        self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
 
243
        self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
 
244
        self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
 
245
        self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
246
246
 
247
247
    def test_heads_two_heads(self):
248
248
        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']))
 
249
        self.assertEqual({'rev2a', 'rev2b'},
 
250
                         graph.heads(['rev2a', 'rev2b']))
 
251
        self.assertEqual({'rev3', 'rev2b'},
 
252
                         graph.heads(['rev3', 'rev2b']))
253
253
 
254
254
    def test_heads_criss_cross(self):
255
255
        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']))
 
256
        self.assertEqual({'rev2a'},
 
257
                         graph.heads(['rev2a', 'rev1']))
 
258
        self.assertEqual({'rev2b'},
 
259
                         graph.heads(['rev2b', 'rev1']))
 
260
        self.assertEqual({'rev3a'},
 
261
                         graph.heads(['rev3a', 'rev1']))
 
262
        self.assertEqual({'rev3b'},
 
263
                         graph.heads(['rev3b', 'rev1']))
 
264
        self.assertEqual({'rev2a', 'rev2b'},
 
265
                         graph.heads(['rev2a', 'rev2b']))
 
266
        self.assertEqual({'rev3a'},
 
267
                         graph.heads(['rev3a', 'rev2a']))
 
268
        self.assertEqual({'rev3a'},
 
269
                         graph.heads(['rev3a', 'rev2b']))
 
270
        self.assertEqual({'rev3a'},
 
271
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
272
        self.assertEqual({'rev3b'},
 
273
                         graph.heads(['rev3b', 'rev2a']))
 
274
        self.assertEqual({'rev3b'},
 
275
                         graph.heads(['rev3b', 'rev2b']))
 
276
        self.assertEqual({'rev3b'},
 
277
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
278
        self.assertEqual({'rev3a', 'rev3b'},
 
279
                         graph.heads(['rev3a', 'rev3b']))
 
280
        self.assertEqual({'rev3a', 'rev3b'},
 
281
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
282
282
 
283
283
    def test_heads_shortcut(self):
284
284
        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']))
 
285
        self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
 
286
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
287
        self.assertEqual({'rev3a', 'rev3b'},
 
288
                         graph.heads(['rev3a', 'rev3b']))
 
289
        self.assertEqual({'rev3a', 'rev3b'},
 
290
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
291
        self.assertEqual({'rev2a', 'rev3b'},
 
292
                         graph.heads(['rev2a', 'rev3b']))
 
293
        self.assertEqual({'rev2c', 'rev3a'},
 
294
                         graph.heads(['rev2c', 'rev3a']))
295
295
 
296
296
    def test_heads_linear(self):
297
297
        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']))
 
298
        self.assertEqual({'w'}, graph.heads(['w', 's']))
 
299
        self.assertEqual({'z'}, graph.heads(['w', 's', 'z']))
 
300
        self.assertEqual({'w', 'q'}, graph.heads(['w', 's', 'q']))
 
301
        self.assertEqual({'z'}, graph.heads(['s', 'z']))
302
302
 
303
303
    def test_heads_alt_merge(self):
304
304
        graph = self.make_known_graph(alt_merge)
305
 
        self.assertEqual({b'c'}, graph.heads([b'a', b'c']))
 
305
        self.assertEqual({'c'}, graph.heads(['a', 'c']))
306
306
 
307
307
    def test_heads_with_ghost(self):
308
308
        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']))
 
309
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
 
310
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c']))
 
311
        self.assertEqual({'a', 'g'}, graph.heads(['a', 'g']))
 
312
        self.assertEqual({'f', 'g'}, graph.heads(['f', 'g']))
 
313
        self.assertEqual({'c'}, graph.heads(['c', 'g']))
 
314
        self.assertEqual({'c'}, graph.heads(['c', 'b', 'd', 'g']))
 
315
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'e', 'g']))
 
316
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'f']))
317
317
 
318
318
    def test_filling_in_ghosts_resets_head_cache(self):
319
319
        graph = self.make_known_graph(test_graph.with_ghost)
320
 
        self.assertEqual({b'e', b'g'}, graph.heads([b'e', b'g']))
 
320
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
321
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
322
322
        # different
323
 
        graph.add_node(b'g', [b'e'])
324
 
        self.assertEqual({b'g'}, graph.heads([b'e', b'g']))
 
323
        graph.add_node('g', ['e'])
 
324
        self.assertEqual({'g'}, graph.heads(['e', 'g']))
325
325
 
326
326
 
327
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
359
359
    def test_topo_sort_cycle(self):
360
360
        """TopoSort traps graph with cycles"""
361
361
        g = self.make_known_graph({0: [1],
362
 
                                   1: [0]})
 
362
                                  1: [0]})
363
363
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
364
364
 
365
365
    def test_topo_sort_cycle_2(self):
484
484
                 'F': ['B', 'D'],
485
485
                 }
486
486
        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
 
                                   ])
 
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
             ])
493
493
        # A
494
494
        # |
495
495
        # B-.
507
507
                 'F': ['B', 'D'],
508
508
                 }
509
509
        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
 
                                   ])
 
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
             ])
517
517
 
518
518
    def test_merge_depth_with_nested_merges(self):
519
519
        # the merge depth marker should reflect the depth of the revision
538
538
             'H': []
539
539
             },
540
540
            'A',
541
 
            [('A', 0, (3,), False),
 
541
            [('A', 0, (3,),  False),
542
542
             ('B', 1, (1, 3, 2), False),
543
543
             ('C', 1, (1, 3, 1), True),
544
544
             ('D', 0, (2,), False),
574
574
             'J': ['G', 'H'],
575
575
             'K': ['I'],
576
576
             'L': ['J', 'K'],
577
 
             },
 
577
            },
578
578
            'L',
579
579
            [('L', 0, (6,), False),
580
580
             ('K', 1, (1, 3, 2), False),
587
587
             ('C', 1, (1, 1, 1), True),
588
588
             ('D', 0, (3,), False),
589
589
             ('B', 0, (2,), False),
590
 
             ('A', 0, (1,), True),
 
590
             ('A', 0, (1,),  True),
591
591
             ],
592
592
            )
593
593
        # Adding a shortcut from the first revision should not change any of
607
607
             'L': ['J', 'K'],
608
608
             'M': ['A'],
609
609
             'N': ['L', 'M'],
610
 
             },
 
610
            },
611
611
            'N',
612
612
            [('N', 0, (7,), False),
613
613
             ('M', 1, (1, 4, 1), True),
622
622
             ('C', 1, (1, 1, 1), True),
623
623
             ('D', 0, (3,), False),
624
624
             ('B', 0, (2,), False),
625
 
             ('A', 0, (1,), True),
 
625
             ('A', 0, (1,),  True),
626
626
             ],
627
627
            )
628
628
 
709
709
        # root: A: []
710
710
        self.assertSortAndIterate(
711
711
            {'J': ['G', 'I'],
712
 
             'I': ['H', ],
 
712
             'I': ['H',],
713
713
             'H': ['A'],
714
714
             'G': ['D', 'F'],
715
715
             'F': ['E'],
768
768
             'P': ['N'],
769
769
             'Q': ['O', 'P'],
770
770
             'R': ['J', 'Q'],
771
 
             },
 
771
            },
772
772
            'R',
773
773
            [('R', 0, (6,), False),
774
774
             ('Q', 1, (0, 4, 5), False),
802
802
            {'A': [],
803
803
             'B': ['A'],
804
804
             'C': ['B', 'ghost'],
805
 
             },
 
805
            },
806
806
            'C',
807
807
            [('C', 0, (3,), False),
808
808
             ('B', 0, (2,), False),
809
809
             ('A', 0, (1,), True),
810
 
             ])
 
810
            ])
811
811
 
812
812
    def test_lefthand_ghost(self):
813
813
        # ghost
818
818
        self.assertSortAndIterate(
819
819
            {'A': ['ghost'],
820
820
             'B': ['A'],
821
 
             }, 'B',
 
821
            }, 'B',
822
822
            [('B', 0, (2,), False),
823
823
             ('A', 0, (1,), True),
824
 
             ])
 
824
            ])
825
825
 
826
826
    def test_graph_cycle(self):
827
827
        # merge_sort should fail with a simple error when a graph cycle is
837
837
        # |'-'
838
838
        # E
839
839
        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
 
                          [])
 
840
            self.assertSortAndIterate,
 
841
                {'A': [],
 
842
                 'B': ['D'],
 
843
                 'C': ['B'],
 
844
                 'D': ['C'],
 
845
                 'E': ['D'],
 
846
                },
 
847
                'E',
 
848
                [])
849
849
 
850
850
 
851
851
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
862
862
        self.assertSorted([], {})
863
863
 
864
864
    def test_single(self):
865
 
        self.assertSorted(['a'], {'a': ()})
866
 
        self.assertSorted([('a',)], {('a',): ()})
867
 
        self.assertSorted([('F', 'a')], {('F', 'a'): ()})
 
865
        self.assertSorted(['a'], {'a':()})
 
866
        self.assertSorted([('a',)], {('a',):()})
 
867
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
868
868
 
869
869
    def test_linear(self):
870
 
        self.assertSorted(['c', 'b', 'a'], {'a': (), 'b': ('a',), 'c': ('b',)})
 
870
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
871
871
        self.assertSorted([('c',), ('b',), ('a',)],
872
 
                          {('a',): (), ('b',): (('a',),), ('c',): (('b',),)})
 
872
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
873
873
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
874
 
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
 
874
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
875
875
                           ('F', 'c'): (('F', 'b'),)})
876
876
 
877
877
    def test_mixed_ancestries(self):
879
879
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
880
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
881
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
882
 
                           ],
 
882
                          ],
883
883
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
884
884
                           ('F', 'c'): (('F', 'b'),),
885
885
                           ('G', 'a'): (), ('G', 'b'): (('G', 'a'),),
886
886
                           ('G', 'c'): (('G', 'b'),),
887
887
                           ('Q', 'a'): (), ('Q', 'b'): (('Q', 'a'),),
888
888
                           ('Q', 'c'): (('Q', 'b'),),
889
 
                           })
 
889
                          })
890
890
 
891
891
    def test_stable_sorting(self):
892
892
        # the sort order should be stable even when extra nodes are added
893
893
        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',)})
 
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',)})
899
899
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
900
 
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
901
 
                           'Z': ('a',)})
 
900
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
901
                           'Z':('a',)})
902
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
903
903
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
904
904
                           'Z': ('a',),
908
908
 
909
909
    def test_skip_ghost(self):
910
910
        self.assertSorted(['b', 'c', 'a'],
911
 
                          {'a': (), 'b': ('a', 'ghost'), 'c': ('a',)})
 
911
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
912
912
 
913
913
    def test_skip_mainline_ghost(self):
914
914
        self.assertSorted(['b', 'c', 'a'],
915
 
                          {'a': (), 'b': ('ghost', 'a'), 'c': ('a',)})
 
915
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})