/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

Finish the pycurl feature.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
 
1
# Copyright (C) 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Tests for the python and pyrex extensions of KnownGraph"""
 
18
 
 
19
import pprint
 
20
 
 
21
from bzrlib import (
 
22
    errors,
 
23
    graph as _mod_graph,
 
24
    _known_graph_py,
 
25
    tests,
 
26
    )
 
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."""
 
33
    scenarios = [
 
34
        ('python', {'module': _known_graph_py, 'do_cache': True}),
 
35
    ]
 
36
    caching_scenarios = [
 
37
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
38
    ]
 
39
    suite = loader.suiteClass()
 
40
    if compiled_known_graph.available():
 
41
        scenarios.append(('C', {'module': compiled_known_graph.module,
 
42
                                'do_cache': True}))
 
43
        caching_scenarios.append(
 
44
            ('C-nocache', {'module': compiled_known_graph.module,
 
45
                           '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)
 
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 = tests.ModuleAvailableFeature('bzrlib._known_graph_pyx')
 
63
 
 
64
 
 
65
#  a
 
66
#  |\
 
67
#  b |
 
68
#  | |
 
69
#  c |
 
70
#   \|
 
71
#    d
 
72
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
 
73
 
 
74
 
 
75
class TestCaseWithKnownGraph(tests.TestCase):
 
76
 
 
77
    module = None # Set by load_tests
 
78
 
 
79
    def make_known_graph(self, ancestry):
 
80
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
 
81
 
 
82
 
 
83
class TestKnownGraph(TestCaseWithKnownGraph):
 
84
 
 
85
    def assertGDFO(self, graph, rev, gdfo):
 
86
        node = graph._nodes[rev]
 
87
        self.assertEqual(gdfo, node.gdfo)
 
88
 
 
89
    def test_children_ancestry1(self):
 
90
        graph = self.make_known_graph(test_graph.ancestry_1)
 
91
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
 
92
        self.assertEqual(['rev2a', 'rev2b'],
 
93
                         sorted(graph.get_child_keys('rev1')))
 
94
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
 
95
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
 
96
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
 
97
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
98
 
 
99
    def test_parent_ancestry1(self):
 
100
        graph = self.make_known_graph(test_graph.ancestry_1)
 
101
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
 
102
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
 
103
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
 
104
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
 
105
        self.assertEqual(['rev2b', 'rev3'],
 
106
                         sorted(graph.get_parent_keys('rev4')))
 
107
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
108
    
 
109
    def test_parent_with_ghost(self):
 
110
        graph = self.make_known_graph(test_graph.with_ghost)
 
111
        self.assertEqual(None, graph.get_parent_keys('g'))
 
112
 
 
113
    def test_gdfo_ancestry_1(self):
 
114
        graph = self.make_known_graph(test_graph.ancestry_1)
 
115
        self.assertGDFO(graph, 'rev1', 2)
 
116
        self.assertGDFO(graph, 'rev2b', 3)
 
117
        self.assertGDFO(graph, 'rev2a', 3)
 
118
        self.assertGDFO(graph, 'rev3', 4)
 
119
        self.assertGDFO(graph, 'rev4', 5)
 
120
 
 
121
    def test_gdfo_feature_branch(self):
 
122
        graph = self.make_known_graph(test_graph.feature_branch)
 
123
        self.assertGDFO(graph, 'rev1', 2)
 
124
        self.assertGDFO(graph, 'rev2b', 3)
 
125
        self.assertGDFO(graph, 'rev3b', 4)
 
126
 
 
127
    def test_gdfo_extended_history_shortcut(self):
 
128
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
129
        self.assertGDFO(graph, 'a', 2)
 
130
        self.assertGDFO(graph, 'b', 3)
 
131
        self.assertGDFO(graph, 'c', 4)
 
132
        self.assertGDFO(graph, 'd', 5)
 
133
        self.assertGDFO(graph, 'e', 6)
 
134
        self.assertGDFO(graph, 'f', 6)
 
135
 
 
136
    def test_gdfo_with_ghost(self):
 
137
        graph = self.make_known_graph(test_graph.with_ghost)
 
138
        self.assertGDFO(graph, 'f', 2)
 
139
        self.assertGDFO(graph, 'e', 3)
 
140
        self.assertGDFO(graph, 'g', 1)
 
141
        self.assertGDFO(graph, 'b', 4)
 
142
        self.assertGDFO(graph, 'd', 4)
 
143
        self.assertGDFO(graph, 'a', 5)
 
144
        self.assertGDFO(graph, 'c', 5)
 
145
 
 
146
    def test_add_existing_node(self):
 
147
        graph = self.make_known_graph(test_graph.ancestry_1)
 
148
        # Add a node that already exists with identical content
 
149
        # This is a 'no-op'
 
150
        self.assertGDFO(graph, 'rev4', 5)
 
151
        graph.add_node('rev4', ['rev3', 'rev2b'])
 
152
        self.assertGDFO(graph, 'rev4', 5)
 
153
        # This also works if we use a tuple rather than a list
 
154
        graph.add_node('rev4', ('rev3', 'rev2b'))
 
155
 
 
156
    def test_add_existing_node_mismatched_parents(self):
 
157
        graph = self.make_known_graph(test_graph.ancestry_1)
 
158
        self.assertRaises(ValueError, graph.add_node, 'rev4',
 
159
                          ['rev2b', 'rev3'])
 
160
 
 
161
    def test_add_node_with_ghost_parent(self):
 
162
        graph = self.make_known_graph(test_graph.ancestry_1)
 
163
        graph.add_node('rev5', ['rev2b', 'revGhost'])
 
164
        self.assertGDFO(graph, 'rev5', 4)
 
165
        self.assertGDFO(graph, 'revGhost', 1)
 
166
 
 
167
    def test_add_new_root(self):
 
168
        graph = self.make_known_graph(test_graph.ancestry_1)
 
169
        graph.add_node('rev5', [])
 
170
        self.assertGDFO(graph, 'rev5', 1)
 
171
 
 
172
    def test_add_with_all_ghost_parents(self):
 
173
        graph = self.make_known_graph(test_graph.ancestry_1)
 
174
        graph.add_node('rev5', ['ghost'])
 
175
        self.assertGDFO(graph, 'rev5', 2)
 
176
        self.assertGDFO(graph, 'ghost', 1)
 
177
 
 
178
    def test_gdfo_after_add_node(self):
 
179
        graph = self.make_known_graph(test_graph.ancestry_1)
 
180
        self.assertEqual([], graph.get_child_keys('rev4'))
 
181
        graph.add_node('rev5', ['rev4'])
 
182
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
 
183
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
 
184
        self.assertEqual([], graph.get_child_keys('rev5'))
 
185
        self.assertGDFO(graph, 'rev5', 6)
 
186
        graph.add_node('rev6', ['rev2b'])
 
187
        graph.add_node('rev7', ['rev6'])
 
188
        graph.add_node('rev8', ['rev7', 'rev5'])
 
189
        self.assertGDFO(graph, 'rev5', 6)
 
190
        self.assertGDFO(graph, 'rev6', 4)
 
191
        self.assertGDFO(graph, 'rev7', 5)
 
192
        self.assertGDFO(graph, 'rev8', 7)
 
193
 
 
194
    def test_fill_in_ghost(self):
 
195
        graph = self.make_known_graph(test_graph.with_ghost)
 
196
        # Add in a couple nodes and then fill in the 'ghost' so that it should
 
197
        # cause renumbering of children nodes
 
198
        graph.add_node('x', [])
 
199
        graph.add_node('y', ['x'])
 
200
        graph.add_node('z', ['y'])
 
201
        graph.add_node('g', ['z'])
 
202
        self.assertGDFO(graph, 'f', 2)
 
203
        self.assertGDFO(graph, 'e', 3)
 
204
        self.assertGDFO(graph, 'x', 1)
 
205
        self.assertGDFO(graph, 'y', 2)
 
206
        self.assertGDFO(graph, 'z', 3)
 
207
        self.assertGDFO(graph, 'g', 4)
 
208
        self.assertGDFO(graph, 'b', 4)
 
209
        self.assertGDFO(graph, 'd', 5)
 
210
        self.assertGDFO(graph, 'a', 5)
 
211
        self.assertGDFO(graph, 'c', 6)
 
212
 
 
213
 
 
214
class TestKnownGraphHeads(TestCaseWithKnownGraph):
 
215
 
 
216
    do_cache = None # Set by load_tests
 
217
 
 
218
    def test_heads_null(self):
 
219
        graph = self.make_known_graph(test_graph.ancestry_1)
 
220
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
221
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
222
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
223
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
224
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
225
 
 
226
    def test_heads_one(self):
 
227
        # A single node will always be a head
 
228
        graph = self.make_known_graph(test_graph.ancestry_1)
 
229
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
230
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
231
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
232
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
233
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
234
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
235
 
 
236
    def test_heads_single(self):
 
237
        graph = self.make_known_graph(test_graph.ancestry_1)
 
238
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
239
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
240
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
241
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
242
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
 
243
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
244
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
245
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
246
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
247
 
 
248
    def test_heads_two_heads(self):
 
249
        graph = self.make_known_graph(test_graph.ancestry_1)
 
250
        self.assertEqual(set(['rev2a', 'rev2b']),
 
251
                         graph.heads(['rev2a', 'rev2b']))
 
252
        self.assertEqual(set(['rev3', 'rev2b']),
 
253
                         graph.heads(['rev3', 'rev2b']))
 
254
 
 
255
    def test_heads_criss_cross(self):
 
256
        graph = self.make_known_graph(test_graph.criss_cross)
 
257
        self.assertEqual(set(['rev2a']),
 
258
                         graph.heads(['rev2a', 'rev1']))
 
259
        self.assertEqual(set(['rev2b']),
 
260
                         graph.heads(['rev2b', 'rev1']))
 
261
        self.assertEqual(set(['rev3a']),
 
262
                         graph.heads(['rev3a', 'rev1']))
 
263
        self.assertEqual(set(['rev3b']),
 
264
                         graph.heads(['rev3b', 'rev1']))
 
265
        self.assertEqual(set(['rev2a', 'rev2b']),
 
266
                         graph.heads(['rev2a', 'rev2b']))
 
267
        self.assertEqual(set(['rev3a']),
 
268
                         graph.heads(['rev3a', 'rev2a']))
 
269
        self.assertEqual(set(['rev3a']),
 
270
                         graph.heads(['rev3a', 'rev2b']))
 
271
        self.assertEqual(set(['rev3a']),
 
272
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
273
        self.assertEqual(set(['rev3b']),
 
274
                         graph.heads(['rev3b', 'rev2a']))
 
275
        self.assertEqual(set(['rev3b']),
 
276
                         graph.heads(['rev3b', 'rev2b']))
 
277
        self.assertEqual(set(['rev3b']),
 
278
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
279
        self.assertEqual(set(['rev3a', 'rev3b']),
 
280
                         graph.heads(['rev3a', 'rev3b']))
 
281
        self.assertEqual(set(['rev3a', 'rev3b']),
 
282
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
283
 
 
284
    def test_heads_shortcut(self):
 
285
        graph = self.make_known_graph(test_graph.history_shortcut)
 
286
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
287
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
288
        self.assertEqual(set(['rev3a', 'rev3b']),
 
289
                         graph.heads(['rev3a', 'rev3b']))
 
290
        self.assertEqual(set(['rev3a', 'rev3b']),
 
291
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
292
        self.assertEqual(set(['rev2a', 'rev3b']),
 
293
                         graph.heads(['rev2a', 'rev3b']))
 
294
        self.assertEqual(set(['rev2c', 'rev3a']),
 
295
                         graph.heads(['rev2c', 'rev3a']))
 
296
 
 
297
    def test_heads_linear(self):
 
298
        graph = self.make_known_graph(test_graph.racing_shortcuts)
 
299
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
 
300
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
 
301
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
 
302
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
303
 
 
304
    def test_heads_alt_merge(self):
 
305
        graph = self.make_known_graph(alt_merge)
 
306
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
 
307
 
 
308
    def test_heads_with_ghost(self):
 
309
        graph = self.make_known_graph(test_graph.with_ghost)
 
310
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
311
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
 
312
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
 
313
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
 
314
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
 
315
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
 
316
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
 
317
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
 
318
 
 
319
    def test_filling_in_ghosts_resets_head_cache(self):
 
320
        graph = self.make_known_graph(test_graph.with_ghost)
 
321
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
322
        # 'g' is filled in, and decends from 'e', so the heads result is now
 
323
        # different
 
324
        graph.add_node('g', ['e'])
 
325
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
 
326
 
 
327
 
 
328
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
 
329
 
 
330
    def assertTopoSortOrder(self, ancestry):
 
331
        """Check topo_sort and iter_topo_order is genuinely topological order.
 
332
 
 
333
        For every child in the graph, check if it comes after all of it's
 
334
        parents.
 
335
        """
 
336
        graph = self.make_known_graph(ancestry)
 
337
        sort_result = graph.topo_sort()
 
338
        # We should have an entry in sort_result for every entry present in the
 
339
        # graph.
 
340
        self.assertEqual(len(ancestry), len(sort_result))
 
341
        node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
 
342
        for node in sort_result:
 
343
            parents = ancestry[node]
 
344
            for parent in parents:
 
345
                if parent not in ancestry:
 
346
                    # ghost
 
347
                    continue
 
348
                if node_idx[node] <= node_idx[parent]:
 
349
                    self.fail("parent %s must come before child %s:\n%s"
 
350
                              % (parent, node, sort_result))
 
351
 
 
352
    def test_topo_sort_empty(self):
 
353
        """TopoSort empty list"""
 
354
        self.assertTopoSortOrder({})
 
355
 
 
356
    def test_topo_sort_easy(self):
 
357
        """TopoSort list with one node"""
 
358
        self.assertTopoSortOrder({0: []})
 
359
 
 
360
    def test_topo_sort_cycle(self):
 
361
        """TopoSort traps graph with cycles"""
 
362
        g = self.make_known_graph({0: [1],
 
363
                                  1: [0]})
 
364
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
365
 
 
366
    def test_topo_sort_cycle_2(self):
 
367
        """TopoSort traps graph with longer cycle"""
 
368
        g = self.make_known_graph({0: [1],
 
369
                                   1: [2],
 
370
                                   2: [0]})
 
371
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
372
 
 
373
    def test_topo_sort_cycle_with_tail(self):
 
374
        """TopoSort traps graph with longer cycle"""
 
375
        g = self.make_known_graph({0: [1],
 
376
                                   1: [2],
 
377
                                   2: [3, 4],
 
378
                                   3: [0],
 
379
                                   4: []})
 
380
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
381
 
 
382
    def test_topo_sort_1(self):
 
383
        """TopoSort simple nontrivial graph"""
 
384
        self.assertTopoSortOrder({0: [3],
 
385
                                  1: [4],
 
386
                                  2: [1, 4],
 
387
                                  3: [],
 
388
                                  4: [0, 3]})
 
389
 
 
390
    def test_topo_sort_partial(self):
 
391
        """Topological sort with partial ordering.
 
392
 
 
393
        Multiple correct orderings are possible, so test for
 
394
        correctness, not for exact match on the resulting list.
 
395
        """
 
396
        self.assertTopoSortOrder({0: [],
 
397
                                  1: [0],
 
398
                                  2: [0],
 
399
                                  3: [0],
 
400
                                  4: [1, 2, 3],
 
401
                                  5: [1, 2],
 
402
                                  6: [1, 2],
 
403
                                  7: [2, 3],
 
404
                                  8: [0, 1, 4, 5, 6]})
 
405
 
 
406
    def test_topo_sort_ghost_parent(self):
 
407
        """Sort nodes, but don't include some parents in the output"""
 
408
        self.assertTopoSortOrder({0: [1],
 
409
                                  1: [2]})
 
410
 
 
411
 
 
412
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
 
413
 
 
414
    def assertSortAndIterate(self, ancestry, branch_tip, result_list):
 
415
        """Check that merge based sorting and iter_topo_order on graph works."""
 
416
        graph = self.make_known_graph(ancestry)
 
417
        value = graph.merge_sort(branch_tip)
 
418
        value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
 
419
                 for n in value]
 
420
        if result_list != value:
 
421
            self.assertEqualDiff(pprint.pformat(result_list),
 
422
                                 pprint.pformat(value))
 
423
 
 
424
    def test_merge_sort_empty(self):
 
425
        # sorting of an emptygraph does not error
 
426
        self.assertSortAndIterate({}, None, [])
 
427
        self.assertSortAndIterate({}, NULL_REVISION, [])
 
428
        self.assertSortAndIterate({}, (NULL_REVISION,), [])
 
429
 
 
430
    def test_merge_sort_not_empty_no_tip(self):
 
431
        # merge sorting of a branch starting with None should result
 
432
        # in an empty list: no revisions are dragged in.
 
433
        self.assertSortAndIterate({0: []}, None, [])
 
434
        self.assertSortAndIterate({0: []}, NULL_REVISION, [])
 
435
        self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
 
436
 
 
437
    def test_merge_sort_one_revision(self):
 
438
        # sorting with one revision as the tip returns the correct fields:
 
439
        # sequence - 0, revision id, merge depth - 0, end_of_merge
 
440
        self.assertSortAndIterate({'id': []},
 
441
                                  'id',
 
442
                                  [('id', 0, (1,), True)])
 
443
 
 
444
    def test_sequence_numbers_increase_no_merges(self):
 
445
        # emit a few revisions with no merges to check the sequence
 
446
        # numbering works in trivial cases
 
447
        self.assertSortAndIterate(
 
448
            {'A': [],
 
449
             'B': ['A'],
 
450
             'C': ['B']},
 
451
            'C',
 
452
            [('C', 0, (3,), False),
 
453
             ('B', 0, (2,), False),
 
454
             ('A', 0, (1,), True),
 
455
             ],
 
456
            )
 
457
 
 
458
    def test_sequence_numbers_increase_with_merges(self):
 
459
        # test that sequence numbers increase across merges
 
460
        self.assertSortAndIterate(
 
461
            {'A': [],
 
462
             'B': ['A'],
 
463
             'C': ['A', 'B']},
 
464
            'C',
 
465
            [('C', 0, (2,), False),
 
466
             ('B', 1, (1,1,1), True),
 
467
             ('A', 0, (1,), True),
 
468
             ],
 
469
            )
 
470
 
 
471
    def test_merge_sort_race(self):
 
472
        # A
 
473
        # |
 
474
        # B-.
 
475
        # |\ \
 
476
        # | | C
 
477
        # | |/
 
478
        # | D
 
479
        # |/
 
480
        # F
 
481
        graph = {'A': [],
 
482
                 'B': ['A'],
 
483
                 'C': ['B'],
 
484
                 'D': ['B', 'C'],
 
485
                 'F': ['B', 'D'],
 
486
                 }
 
487
        self.assertSortAndIterate(graph, 'F',
 
488
            [('F', 0, (3,), False),
 
489
             ('D', 1, (2,2,1), False),
 
490
             ('C', 2, (2,1,1), True),
 
491
             ('B', 0, (2,), False),
 
492
             ('A', 0, (1,), True),
 
493
             ])
 
494
        # A
 
495
        # |
 
496
        # B-.
 
497
        # |\ \
 
498
        # | X C
 
499
        # | |/
 
500
        # | D
 
501
        # |/
 
502
        # F
 
503
        graph = {'A': [],
 
504
                 'B': ['A'],
 
505
                 'C': ['B'],
 
506
                 'X': ['B'],
 
507
                 'D': ['X', 'C'],
 
508
                 'F': ['B', 'D'],
 
509
                 }
 
510
        self.assertSortAndIterate(graph, 'F',
 
511
            [('F', 0, (3,), False),
 
512
             ('D', 1, (2,1,2), False),
 
513
             ('C', 2, (2,2,1), True),
 
514
             ('X', 1, (2,1,1), True),
 
515
             ('B', 0, (2,), False),
 
516
             ('A', 0, (1,), True),
 
517
             ])
 
518
 
 
519
    def test_merge_depth_with_nested_merges(self):
 
520
        # the merge depth marker should reflect the depth of the revision
 
521
        # in terms of merges out from the mainline
 
522
        # revid, depth, parents:
 
523
        #  A 0   [D, B]
 
524
        #  B  1  [C, F]
 
525
        #  C  1  [H]
 
526
        #  D 0   [H, E]
 
527
        #  E  1  [G, F]
 
528
        #  F   2 [G]
 
529
        #  G  1  [H]
 
530
        #  H 0
 
531
        self.assertSortAndIterate(
 
532
            {'A': ['D', 'B'],
 
533
             'B': ['C', 'F'],
 
534
             'C': ['H'],
 
535
             'D': ['H', 'E'],
 
536
             'E': ['G', 'F'],
 
537
             'F': ['G'],
 
538
             'G': ['H'],
 
539
             'H': []
 
540
             },
 
541
            'A',
 
542
            [('A', 0, (3,),  False),
 
543
             ('B', 1, (1,3,2), False),
 
544
             ('C', 1, (1,3,1), True),
 
545
             ('D', 0, (2,), False),
 
546
             ('E', 1, (1,1,2), False),
 
547
             ('F', 2, (1,2,1), True),
 
548
             ('G', 1, (1,1,1), True),
 
549
             ('H', 0, (1,), True),
 
550
             ],
 
551
            )
 
552
 
 
553
    def test_dotted_revnos_with_simple_merges(self):
 
554
        # A         1
 
555
        # |\
 
556
        # B C       2, 1.1.1
 
557
        # | |\
 
558
        # D E F     3, 1.1.2, 1.2.1
 
559
        # |/ /|
 
560
        # G H I     4, 1.2.2, 1.3.1
 
561
        # |/ /
 
562
        # J K       5, 1.3.2
 
563
        # |/
 
564
        # L         6
 
565
        self.assertSortAndIterate(
 
566
            {'A': [],
 
567
             'B': ['A'],
 
568
             'C': ['A'],
 
569
             'D': ['B'],
 
570
             'E': ['C'],
 
571
             'F': ['C'],
 
572
             'G': ['D', 'E'],
 
573
             'H': ['F'],
 
574
             'I': ['F'],
 
575
             'J': ['G', 'H'],
 
576
             'K': ['I'],
 
577
             'L': ['J', 'K'],
 
578
            },
 
579
            'L',
 
580
            [('L', 0, (6,), False),
 
581
             ('K', 1, (1,3,2), False),
 
582
             ('I', 1, (1,3,1), True),
 
583
             ('J', 0, (5,), False),
 
584
             ('H', 1, (1,2,2), False),
 
585
             ('F', 1, (1,2,1), True),
 
586
             ('G', 0, (4,), False),
 
587
             ('E', 1, (1,1,2), False),
 
588
             ('C', 1, (1,1,1), True),
 
589
             ('D', 0, (3,), False),
 
590
             ('B', 0, (2,), False),
 
591
             ('A', 0, (1,),  True),
 
592
             ],
 
593
            )
 
594
        # Adding a shortcut from the first revision should not change any of
 
595
        # the existing numbers
 
596
        self.assertSortAndIterate(
 
597
            {'A': [],
 
598
             'B': ['A'],
 
599
             'C': ['A'],
 
600
             'D': ['B'],
 
601
             'E': ['C'],
 
602
             'F': ['C'],
 
603
             'G': ['D', 'E'],
 
604
             'H': ['F'],
 
605
             'I': ['F'],
 
606
             'J': ['G', 'H'],
 
607
             'K': ['I'],
 
608
             'L': ['J', 'K'],
 
609
             'M': ['A'],
 
610
             'N': ['L', 'M'],
 
611
            },
 
612
            'N',
 
613
            [('N', 0, (7,), False),
 
614
             ('M', 1, (1,4,1), True),
 
615
             ('L', 0, (6,), False),
 
616
             ('K', 1, (1,3,2), False),
 
617
             ('I', 1, (1,3,1), True),
 
618
             ('J', 0, (5,), False),
 
619
             ('H', 1, (1,2,2), False),
 
620
             ('F', 1, (1,2,1), True),
 
621
             ('G', 0, (4,), False),
 
622
             ('E', 1, (1,1,2), False),
 
623
             ('C', 1, (1,1,1), True),
 
624
             ('D', 0, (3,), False),
 
625
             ('B', 0, (2,), False),
 
626
             ('A', 0, (1,),  True),
 
627
             ],
 
628
            )
 
629
 
 
630
    def test_end_of_merge_not_last_revision_in_branch(self):
 
631
        # within a branch only the last revision gets an
 
632
        # end of merge marker.
 
633
        self.assertSortAndIterate(
 
634
            {'A': ['B'],
 
635
             'B': [],
 
636
             },
 
637
            'A',
 
638
            [('A', 0, (2,), False),
 
639
             ('B', 0, (1,), True)
 
640
             ],
 
641
            )
 
642
 
 
643
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
 
644
        # when multiple branches are merged at once, both of their
 
645
        # branch-endpoints should be listed as end-of-merge.
 
646
        # Also, the order of the multiple merges should be
 
647
        # left-right shown top to bottom.
 
648
        # * means end of merge
 
649
        # A 0    [H, B, E]
 
650
        # B  1   [D, C]
 
651
        # C   2  [D]       *
 
652
        # D  1   [H]       *
 
653
        # E  1   [G, F]
 
654
        # F   2  [G]       *
 
655
        # G  1   [H]       *
 
656
        # H 0    []        *
 
657
        self.assertSortAndIterate(
 
658
            {'A': ['H', 'B', 'E'],
 
659
             'B': ['D', 'C'],
 
660
             'C': ['D'],
 
661
             'D': ['H'],
 
662
             'E': ['G', 'F'],
 
663
             'F': ['G'],
 
664
             'G': ['H'],
 
665
             'H': [],
 
666
             },
 
667
            'A',
 
668
            [('A', 0, (2,), False),
 
669
             ('B', 1, (1,3,2), False),
 
670
             ('C', 2, (1,4,1), True),
 
671
             ('D', 1, (1,3,1), True),
 
672
             ('E', 1, (1,1,2), False),
 
673
             ('F', 2, (1,2,1), True),
 
674
             ('G', 1, (1,1,1), True),
 
675
             ('H', 0, (1,), True),
 
676
             ],
 
677
            )
 
678
 
 
679
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
 
680
        """When there are parallel roots, check their revnos."""
 
681
        self.assertSortAndIterate(
 
682
            {'A': [],
 
683
             'B': [],
 
684
             'C': ['A', 'B']},
 
685
            'C',
 
686
            [('C', 0, (2,), False),
 
687
             ('B', 1, (0,1,1), True),
 
688
             ('A', 0, (1,), True),
 
689
             ],
 
690
            )
 
691
 
 
692
    def test_revnos_are_globally_assigned(self):
 
693
        """revnos are assigned according to the revision they derive from."""
 
694
        # in this test we setup a number of branches that all derive from
 
695
        # the first revision, and then merge them one at a time, which
 
696
        # should give the revisions as they merge numbers still deriving from
 
697
        # the revision were based on.
 
698
        # merge 3: J: ['G', 'I']
 
699
        # branch 3:
 
700
        #  I: ['H']
 
701
        #  H: ['A']
 
702
        # merge 2: G: ['D', 'F']
 
703
        # branch 2:
 
704
        #  F: ['E']
 
705
        #  E: ['A']
 
706
        # merge 1: D: ['A', 'C']
 
707
        # branch 1:
 
708
        #  C: ['B']
 
709
        #  B: ['A']
 
710
        # root: A: []
 
711
        self.assertSortAndIterate(
 
712
            {'J': ['G', 'I'],
 
713
             'I': ['H',],
 
714
             'H': ['A'],
 
715
             'G': ['D', 'F'],
 
716
             'F': ['E'],
 
717
             'E': ['A'],
 
718
             'D': ['A', 'C'],
 
719
             'C': ['B'],
 
720
             'B': ['A'],
 
721
             'A': [],
 
722
             },
 
723
            'J',
 
724
            [('J', 0, (4,), False),
 
725
             ('I', 1, (1,3,2), False),
 
726
             ('H', 1, (1,3,1), True),
 
727
             ('G', 0, (3,), False),
 
728
             ('F', 1, (1,2,2), False),
 
729
             ('E', 1, (1,2,1), True),
 
730
             ('D', 0, (2,), False),
 
731
             ('C', 1, (1,1,2), False),
 
732
             ('B', 1, (1,1,1), True),
 
733
             ('A', 0, (1,), True),
 
734
             ],
 
735
            )
 
736
 
 
737
    def test_roots_and_sub_branches_versus_ghosts(self):
 
738
        """Extra roots and their mini branches use the same numbering.
 
739
 
 
740
        All of them use the 0-node numbering.
 
741
        """
 
742
        #       A D   K
 
743
        #       | |\  |\
 
744
        #       B E F L M
 
745
        #       | |/  |/
 
746
        #       C G   N
 
747
        #       |/    |\
 
748
        #       H I   O P
 
749
        #       |/    |/
 
750
        #       J     Q
 
751
        #       |.---'
 
752
        #       R
 
753
        self.assertSortAndIterate(
 
754
            {'A': [],
 
755
             'B': ['A'],
 
756
             'C': ['B'],
 
757
             'D': [],
 
758
             'E': ['D'],
 
759
             'F': ['D'],
 
760
             'G': ['E', 'F'],
 
761
             'H': ['C', 'G'],
 
762
             'I': [],
 
763
             'J': ['H', 'I'],
 
764
             'K': [],
 
765
             'L': ['K'],
 
766
             'M': ['K'],
 
767
             'N': ['L', 'M'],
 
768
             'O': ['N'],
 
769
             'P': ['N'],
 
770
             'Q': ['O', 'P'],
 
771
             'R': ['J', 'Q'],
 
772
            },
 
773
            'R',
 
774
            [('R', 0, (6,), False),
 
775
             ('Q', 1, (0,4,5), False),
 
776
             ('P', 2, (0,6,1), True),
 
777
             ('O', 1, (0,4,4), False),
 
778
             ('N', 1, (0,4,3), False),
 
779
             ('M', 2, (0,5,1), True),
 
780
             ('L', 1, (0,4,2), False),
 
781
             ('K', 1, (0,4,1), True),
 
782
             ('J', 0, (5,), False),
 
783
             ('I', 1, (0,3,1), True),
 
784
             ('H', 0, (4,), False),
 
785
             ('G', 1, (0,1,3), False),
 
786
             ('F', 2, (0,2,1), True),
 
787
             ('E', 1, (0,1,2), False),
 
788
             ('D', 1, (0,1,1), True),
 
789
             ('C', 0, (3,), False),
 
790
             ('B', 0, (2,), False),
 
791
             ('A', 0, (1,), True),
 
792
             ],
 
793
            )
 
794
 
 
795
    def test_ghost(self):
 
796
        # merge_sort should be able to ignore ghosts
 
797
        # A
 
798
        # |
 
799
        # B ghost
 
800
        # |/
 
801
        # C
 
802
        self.assertSortAndIterate(
 
803
            {'A': [],
 
804
             'B': ['A'],
 
805
             'C': ['B', 'ghost'],
 
806
            },
 
807
            'C',
 
808
            [('C', 0, (3,), False),
 
809
             ('B', 0, (2,), False),
 
810
             ('A', 0, (1,), True),
 
811
            ])
 
812
 
 
813
    def test_lefthand_ghost(self):
 
814
        # ghost
 
815
        #  |
 
816
        #  A
 
817
        #  |
 
818
        #  B
 
819
        self.assertSortAndIterate(
 
820
            {'A': ['ghost'],
 
821
             'B': ['A'],
 
822
            }, 'B',
 
823
            [('B', 0, (2,), False),
 
824
             ('A', 0, (1,), True),
 
825
            ])
 
826
 
 
827
    def test_graph_cycle(self):
 
828
        # merge_sort should fail with a simple error when a graph cycle is
 
829
        # encountered.
 
830
        #
 
831
        # A
 
832
        # |,-.
 
833
        # B  |
 
834
        # |  |
 
835
        # C  ^
 
836
        # |  |
 
837
        # D  |
 
838
        # |'-'
 
839
        # E
 
840
        self.assertRaises(errors.GraphCycleError,
 
841
            self.assertSortAndIterate,
 
842
                {'A': [],
 
843
                 'B': ['D'],
 
844
                 'C': ['B'],
 
845
                 'D': ['C'],
 
846
                 'E': ['D'],
 
847
                },
 
848
                'E',
 
849
                [])
 
850
 
 
851
 
 
852
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
853
    """Test the sort order returned by gc_sort."""
 
854
 
 
855
    def assertSorted(self, expected, parent_map):
 
856
        graph = self.make_known_graph(parent_map)
 
857
        value = graph.gc_sort()
 
858
        if expected != value:
 
859
            self.assertEqualDiff(pprint.pformat(expected),
 
860
                                 pprint.pformat(value))
 
861
 
 
862
    def test_empty(self):
 
863
        self.assertSorted([], {})
 
864
 
 
865
    def test_single(self):
 
866
        self.assertSorted(['a'], {'a':()})
 
867
        self.assertSorted([('a',)], {('a',):()})
 
868
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
869
 
 
870
    def test_linear(self):
 
871
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
872
        self.assertSorted([('c',), ('b',), ('a',)],
 
873
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
874
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
875
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
876
                           ('F', 'c'): (('F', 'b'),)})
 
877
 
 
878
    def test_mixed_ancestries(self):
 
879
        # Each prefix should be sorted separately
 
880
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
881
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
882
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
883
                          ],
 
884
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
885
                           ('F', 'c'): (('F', 'b'),),
 
886
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
887
                           ('G', 'c'): (('G', 'b'),),
 
888
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
889
                           ('Q', 'c'): (('Q', 'b'),),
 
890
                          })
 
891
 
 
892
    def test_stable_sorting(self):
 
893
        # the sort order should be stable even when extra nodes are added
 
894
        self.assertSorted(['b', 'c', 'a'],
 
895
                          {'a':(), 'b':('a',), 'c':('a',)})
 
896
        self.assertSorted(['b', 'c', 'd', 'a'],
 
897
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
898
        self.assertSorted(['b', 'c', 'd', 'a'],
 
899
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
900
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
901
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
902
                           'Z':('a',)})
 
903
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
904
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
905
                           'Z':('a',),
 
906
                           'e':('b', 'c', 'd'),
 
907
                           'f':('d', 'Z'),
 
908
                           })
 
909
 
 
910
    def test_skip_ghost(self):
 
911
        self.assertSorted(['b', 'c', 'a'],
 
912
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
913
 
 
914
    def test_skip_mainline_ghost(self):
 
915
        self.assertSorted(['b', 'c', 'a'],
 
916
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})