← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: Aaron Bentley
  • Date: 2009-06-19 21:16:31 UTC
  • mto: This revision was merged to the branch mainline in revision 4481.
  • Revision ID: aaron@aaronbentley.com-20090619211631-4fnkv2uui98xj7ux
Provide control over switch and shelver messaging.

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 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
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
"""Tests for the python and pyrex extensions of KnownGraph"""
18
 
 
19
 
import pprint
 
17
"""Tests for the python and pyrex extensions of groupcompress"""
20
18
 
21
19
from bzrlib import (
22
20
    errors,
 
21
    graph as _mod_graph,
23
22
    _known_graph_py,
24
23
    tests,
25
24
    )
26
25
from bzrlib.tests import test_graph
27
26
from bzrlib.revision import NULL_REVISION
28
 
from bzrlib.tests.scenarios import load_tests_apply_scenarios
29
 
from bzrlib.tests import (
30
 
    features,
31
 
    )
32
 
 
33
 
 
34
 
def caching_scenarios():
 
27
 
 
28
 
 
29
def load_tests(standard_tests, module, loader):
 
30
    """Parameterize tests for all versions of groupcompress."""
35
31
    scenarios = [
36
32
        ('python', {'module': _known_graph_py, 'do_cache': True}),
37
 
    ]
38
 
    if compiled_known_graph_feature.available():
39
 
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
40
 
                                'do_cache': True}))
41
 
    return scenarios
42
 
 
43
 
 
44
 
def non_caching_scenarios():
45
 
    scenarios = [
46
33
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
47
34
    ]
48
 
    if compiled_known_graph_feature.available():
49
 
        scenarios.append(
50
 
            ('C-nocache', {'module': compiled_known_graph_feature.module,
51
 
                           '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
 
    'bzrlib._known_graph_pyx')
60
 
 
61
 
 
62
 
#  a
63
 
#  |\
64
 
#  b |
65
 
#  | |
66
 
#  c |
67
 
#   \|
68
 
#    d
69
 
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
70
 
 
71
 
 
72
 
class TestCaseWithKnownGraph(tests.TestCase):
73
 
 
74
 
    scenarios = caching_scenarios()
 
35
    suite = loader.suiteClass()
 
36
    if CompiledKnownGraphFeature.available():
 
37
        from bzrlib import _known_graph_pyx
 
38
        scenarios.append(('C', {'module': _known_graph_pyx, 'do_cache': True}))
 
39
        scenarios.append(('C-nocache',
 
40
                          {'module': _known_graph_pyx, 'do_cache': False}))
 
41
    else:
 
42
        # the compiled module isn't available, so we add a failing test
 
43
        class FailWithoutFeature(tests.TestCase):
 
44
            def test_fail(self):
 
45
                self.requireFeature(CompiledKnownGraphFeature)
 
46
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
 
47
    result = tests.multiply_tests(standard_tests, scenarios, suite)
 
48
    return result
 
49
 
 
50
 
 
51
class _CompiledKnownGraphFeature(tests.Feature):
 
52
 
 
53
    def _probe(self):
 
54
        try:
 
55
            import bzrlib._known_graph_pyx
 
56
        except ImportError:
 
57
            return False
 
58
        return True
 
59
 
 
60
    def feature_name(self):
 
61
        return 'bzrlib._known_graph_pyx'
 
62
 
 
63
CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
 
64
 
 
65
 
 
66
class TestKnownGraph(tests.TestCase):
 
67
 
75
68
    module = None # Set by load_tests
 
69
    do_cache = None # Set by load_tests
76
70
 
77
71
    def make_known_graph(self, ancestry):
78
72
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
79
73
 
80
 
 
81
 
class TestKnownGraph(TestCaseWithKnownGraph):
 
74
    def assertDominator(self, graph, rev, dominator):
 
75
        node = graph._nodes[rev]
 
76
        self.assertEqual(dominator, node.linear_dominator)
82
77
 
83
78
    def assertGDFO(self, graph, rev, gdfo):
84
79
        node = graph._nodes[rev]
86
81
 
87
82
    def test_children_ancestry1(self):
88
83
        graph = self.make_known_graph(test_graph.ancestry_1)
89
 
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
 
84
        self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
90
85
        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')
 
86
                         sorted(graph._nodes['rev1'].child_keys))
 
87
        self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
 
88
        self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
 
89
        self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
96
90
 
97
 
    def test_parent_ancestry1(self):
 
91
    def test_dominators_ancestry_1(self):
98
92
        graph = self.make_known_graph(test_graph.ancestry_1)
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
 
    def test_parent_with_ghost(self):
108
 
        graph = self.make_known_graph(test_graph.with_ghost)
109
 
        self.assertEqual(None, graph.get_parent_keys('g'))
 
93
        self.assertDominator(graph, 'rev1', NULL_REVISION)
 
94
        self.assertDominator(graph, 'rev2b', 'rev2b')
 
95
        self.assertDominator(graph, 'rev2a', 'rev2a')
 
96
        self.assertDominator(graph, 'rev3', 'rev2a')
 
97
        self.assertDominator(graph, 'rev4', 'rev4')
 
98
 
 
99
    def test_dominators_feature_branch(self):
 
100
        graph = self.make_known_graph(test_graph.feature_branch)
 
101
        self.assertDominator(graph, 'rev1', NULL_REVISION)
 
102
        self.assertDominator(graph, 'rev2b', NULL_REVISION)
 
103
        self.assertDominator(graph, 'rev3b', NULL_REVISION)
 
104
 
 
105
    def test_dominators_extended_history_shortcut(self):
 
106
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
107
        self.assertDominator(graph, 'a', NULL_REVISION)
 
108
        self.assertDominator(graph, 'b', 'b')
 
109
        self.assertDominator(graph, 'c', 'b')
 
110
        self.assertDominator(graph, 'd', 'b')
 
111
        self.assertDominator(graph, 'e', 'e')
 
112
        self.assertDominator(graph, 'f', 'f')
110
113
 
111
114
    def test_gdfo_ancestry_1(self):
112
115
        graph = self.make_known_graph(test_graph.ancestry_1)
141
144
        self.assertGDFO(graph, 'a', 5)
142
145
        self.assertGDFO(graph, 'c', 5)
143
146
 
144
 
    def test_add_existing_node(self):
145
 
        graph = self.make_known_graph(test_graph.ancestry_1)
146
 
        # Add a node that already exists with identical content
147
 
        # This is a 'no-op'
148
 
        self.assertGDFO(graph, 'rev4', 5)
149
 
        graph.add_node('rev4', ['rev3', 'rev2b'])
150
 
        self.assertGDFO(graph, 'rev4', 5)
151
 
        # This also works if we use a tuple rather than a list
152
 
        graph.add_node('rev4', ('rev3', 'rev2b'))
153
 
 
154
 
    def test_add_existing_node_mismatched_parents(self):
155
 
        graph = self.make_known_graph(test_graph.ancestry_1)
156
 
        self.assertRaises(ValueError, graph.add_node, 'rev4',
157
 
                          ['rev2b', 'rev3'])
158
 
 
159
 
    def test_add_node_with_ghost_parent(self):
160
 
        graph = self.make_known_graph(test_graph.ancestry_1)
161
 
        graph.add_node('rev5', ['rev2b', 'revGhost'])
162
 
        self.assertGDFO(graph, 'rev5', 4)
163
 
        self.assertGDFO(graph, 'revGhost', 1)
164
 
 
165
 
    def test_add_new_root(self):
166
 
        graph = self.make_known_graph(test_graph.ancestry_1)
167
 
        graph.add_node('rev5', [])
168
 
        self.assertGDFO(graph, 'rev5', 1)
169
 
 
170
 
    def test_add_with_all_ghost_parents(self):
171
 
        graph = self.make_known_graph(test_graph.ancestry_1)
172
 
        graph.add_node('rev5', ['ghost'])
173
 
        self.assertGDFO(graph, 'rev5', 2)
174
 
        self.assertGDFO(graph, 'ghost', 1)
175
 
 
176
 
    def test_gdfo_after_add_node(self):
177
 
        graph = self.make_known_graph(test_graph.ancestry_1)
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
 
 
192
 
    def test_fill_in_ghost(self):
193
 
        graph = self.make_known_graph(test_graph.with_ghost)
194
 
        # Add in a couple nodes and then fill in the 'ghost' so that it should
195
 
        # cause renumbering of children nodes
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
 
 
211
 
 
212
 
class TestKnownGraphHeads(TestCaseWithKnownGraph):
213
 
 
214
 
    scenarios = caching_scenarios() + non_caching_scenarios()
215
 
    do_cache = None # Set by load_tests
216
 
 
217
147
    def test_heads_null(self):
218
148
        graph = self.make_known_graph(test_graph.ancestry_1)
219
149
        self.assertEqual(set(['null:']), graph.heads(['null:']))
299
229
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
300
230
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
301
231
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
302
 
 
303
 
    def test_heads_alt_merge(self):
304
 
        graph = self.make_known_graph(alt_merge)
305
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
306
 
 
307
 
    def test_heads_with_ghost(self):
308
 
        graph = self.make_known_graph(test_graph.with_ghost)
309
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
310
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
311
 
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
312
 
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
313
 
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
314
 
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
315
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
316
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
317
 
 
318
 
    def test_filling_in_ghosts_resets_head_cache(self):
319
 
        graph = self.make_known_graph(test_graph.with_ghost)
320
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
321
 
        # 'g' is filled in, and decends from 'e', so the heads result is now
322
 
        # different
323
 
        graph.add_node('g', ['e'])
324
 
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
325
 
 
326
 
 
327
 
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
328
 
 
329
 
    def assertTopoSortOrder(self, ancestry):
330
 
        """Check topo_sort and iter_topo_order is genuinely topological order.
331
 
 
332
 
        For every child in the graph, check if it comes after all of it's
333
 
        parents.
334
 
        """
335
 
        graph = self.make_known_graph(ancestry)
336
 
        sort_result = graph.topo_sort()
337
 
        # We should have an entry in sort_result for every entry present in the
338
 
        # graph.
339
 
        self.assertEqual(len(ancestry), len(sort_result))
340
 
        node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
341
 
        for node in sort_result:
342
 
            parents = ancestry[node]
343
 
            for parent in parents:
344
 
                if parent not in ancestry:
345
 
                    # ghost
346
 
                    continue
347
 
                if node_idx[node] <= node_idx[parent]:
348
 
                    self.fail("parent %s must come before child %s:\n%s"
349
 
                              % (parent, node, sort_result))
350
 
 
351
 
    def test_topo_sort_empty(self):
352
 
        """TopoSort empty list"""
353
 
        self.assertTopoSortOrder({})
354
 
 
355
 
    def test_topo_sort_easy(self):
356
 
        """TopoSort list with one node"""
357
 
        self.assertTopoSortOrder({0: []})
358
 
 
359
 
    def test_topo_sort_cycle(self):
360
 
        """TopoSort traps graph with cycles"""
361
 
        g = self.make_known_graph({0: [1],
362
 
                                  1: [0]})
363
 
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
364
 
 
365
 
    def test_topo_sort_cycle_2(self):
366
 
        """TopoSort traps graph with longer cycle"""
367
 
        g = self.make_known_graph({0: [1],
368
 
                                   1: [2],
369
 
                                   2: [0]})
370
 
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
371
 
 
372
 
    def test_topo_sort_cycle_with_tail(self):
373
 
        """TopoSort traps graph with longer cycle"""
374
 
        g = self.make_known_graph({0: [1],
375
 
                                   1: [2],
376
 
                                   2: [3, 4],
377
 
                                   3: [0],
378
 
                                   4: []})
379
 
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
380
 
 
381
 
    def test_topo_sort_1(self):
382
 
        """TopoSort simple nontrivial graph"""
383
 
        self.assertTopoSortOrder({0: [3],
384
 
                                  1: [4],
385
 
                                  2: [1, 4],
386
 
                                  3: [],
387
 
                                  4: [0, 3]})
388
 
 
389
 
    def test_topo_sort_partial(self):
390
 
        """Topological sort with partial ordering.
391
 
 
392
 
        Multiple correct orderings are possible, so test for
393
 
        correctness, not for exact match on the resulting list.
394
 
        """
395
 
        self.assertTopoSortOrder({0: [],
396
 
                                  1: [0],
397
 
                                  2: [0],
398
 
                                  3: [0],
399
 
                                  4: [1, 2, 3],
400
 
                                  5: [1, 2],
401
 
                                  6: [1, 2],
402
 
                                  7: [2, 3],
403
 
                                  8: [0, 1, 4, 5, 6]})
404
 
 
405
 
    def test_topo_sort_ghost_parent(self):
406
 
        """Sort nodes, but don't include some parents in the output"""
407
 
        self.assertTopoSortOrder({0: [1],
408
 
                                  1: [2]})
409
 
 
410
 
 
411
 
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
412
 
 
413
 
    def assertSortAndIterate(self, ancestry, branch_tip, result_list):
414
 
        """Check that merge based sorting and iter_topo_order on graph works."""
415
 
        graph = self.make_known_graph(ancestry)
416
 
        value = graph.merge_sort(branch_tip)
417
 
        value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
418
 
                 for n in value]
419
 
        if result_list != value:
420
 
            self.assertEqualDiff(pprint.pformat(result_list),
421
 
                                 pprint.pformat(value))
422
 
 
423
 
    def test_merge_sort_empty(self):
424
 
        # sorting of an emptygraph does not error
425
 
        self.assertSortAndIterate({}, None, [])
426
 
        self.assertSortAndIterate({}, NULL_REVISION, [])
427
 
        self.assertSortAndIterate({}, (NULL_REVISION,), [])
428
 
 
429
 
    def test_merge_sort_not_empty_no_tip(self):
430
 
        # merge sorting of a branch starting with None should result
431
 
        # in an empty list: no revisions are dragged in.
432
 
        self.assertSortAndIterate({0: []}, None, [])
433
 
        self.assertSortAndIterate({0: []}, NULL_REVISION, [])
434
 
        self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
435
 
 
436
 
    def test_merge_sort_one_revision(self):
437
 
        # sorting with one revision as the tip returns the correct fields:
438
 
        # sequence - 0, revision id, merge depth - 0, end_of_merge
439
 
        self.assertSortAndIterate({'id': []},
440
 
                                  'id',
441
 
                                  [('id', 0, (1,), True)])
442
 
 
443
 
    def test_sequence_numbers_increase_no_merges(self):
444
 
        # emit a few revisions with no merges to check the sequence
445
 
        # numbering works in trivial cases
446
 
        self.assertSortAndIterate(
447
 
            {'A': [],
448
 
             'B': ['A'],
449
 
             'C': ['B']},
450
 
            'C',
451
 
            [('C', 0, (3,), False),
452
 
             ('B', 0, (2,), False),
453
 
             ('A', 0, (1,), True),
454
 
             ],
455
 
            )
456
 
 
457
 
    def test_sequence_numbers_increase_with_merges(self):
458
 
        # test that sequence numbers increase across merges
459
 
        self.assertSortAndIterate(
460
 
            {'A': [],
461
 
             'B': ['A'],
462
 
             'C': ['A', 'B']},
463
 
            'C',
464
 
            [('C', 0, (2,), False),
465
 
             ('B', 1, (1,1,1), True),
466
 
             ('A', 0, (1,), True),
467
 
             ],
468
 
            )
469
 
 
470
 
    def test_merge_sort_race(self):
471
 
        # A
472
 
        # |
473
 
        # B-.
474
 
        # |\ \
475
 
        # | | C
476
 
        # | |/
477
 
        # | D
478
 
        # |/
479
 
        # F
480
 
        graph = {'A': [],
481
 
                 'B': ['A'],
482
 
                 'C': ['B'],
483
 
                 'D': ['B', 'C'],
484
 
                 'F': ['B', 'D'],
485
 
                 }
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
 
             ])
493
 
        # A
494
 
        # |
495
 
        # B-.
496
 
        # |\ \
497
 
        # | X C
498
 
        # | |/
499
 
        # | D
500
 
        # |/
501
 
        # F
502
 
        graph = {'A': [],
503
 
                 'B': ['A'],
504
 
                 'C': ['B'],
505
 
                 'X': ['B'],
506
 
                 'D': ['X', 'C'],
507
 
                 'F': ['B', 'D'],
508
 
                 }
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
 
             ])
517
 
 
518
 
    def test_merge_depth_with_nested_merges(self):
519
 
        # the merge depth marker should reflect the depth of the revision
520
 
        # in terms of merges out from the mainline
521
 
        # revid, depth, parents:
522
 
        #  A 0   [D, B]
523
 
        #  B  1  [C, F]
524
 
        #  C  1  [H]
525
 
        #  D 0   [H, E]
526
 
        #  E  1  [G, F]
527
 
        #  F   2 [G]
528
 
        #  G  1  [H]
529
 
        #  H 0
530
 
        self.assertSortAndIterate(
531
 
            {'A': ['D', 'B'],
532
 
             'B': ['C', 'F'],
533
 
             'C': ['H'],
534
 
             'D': ['H', 'E'],
535
 
             'E': ['G', 'F'],
536
 
             'F': ['G'],
537
 
             'G': ['H'],
538
 
             'H': []
539
 
             },
540
 
            'A',
541
 
            [('A', 0, (3,),  False),
542
 
             ('B', 1, (1,3,2), False),
543
 
             ('C', 1, (1,3,1), True),
544
 
             ('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),
548
 
             ('H', 0, (1,), True),
549
 
             ],
550
 
            )
551
 
 
552
 
    def test_dotted_revnos_with_simple_merges(self):
553
 
        # A         1
554
 
        # |\
555
 
        # B C       2, 1.1.1
556
 
        # | |\
557
 
        # D E F     3, 1.1.2, 1.2.1
558
 
        # |/ /|
559
 
        # G H I     4, 1.2.2, 1.3.1
560
 
        # |/ /
561
 
        # J K       5, 1.3.2
562
 
        # |/
563
 
        # L         6
564
 
        self.assertSortAndIterate(
565
 
            {'A': [],
566
 
             'B': ['A'],
567
 
             'C': ['A'],
568
 
             'D': ['B'],
569
 
             'E': ['C'],
570
 
             'F': ['C'],
571
 
             'G': ['D', 'E'],
572
 
             'H': ['F'],
573
 
             'I': ['F'],
574
 
             'J': ['G', 'H'],
575
 
             'K': ['I'],
576
 
             'L': ['J', 'K'],
577
 
            },
578
 
            'L',
579
 
            [('L', 0, (6,), False),
580
 
             ('K', 1, (1,3,2), False),
581
 
             ('I', 1, (1,3,1), True),
582
 
             ('J', 0, (5,), False),
583
 
             ('H', 1, (1,2,2), False),
584
 
             ('F', 1, (1,2,1), True),
585
 
             ('G', 0, (4,), False),
586
 
             ('E', 1, (1,1,2), False),
587
 
             ('C', 1, (1,1,1), True),
588
 
             ('D', 0, (3,), False),
589
 
             ('B', 0, (2,), False),
590
 
             ('A', 0, (1,),  True),
591
 
             ],
592
 
            )
593
 
        # Adding a shortcut from the first revision should not change any of
594
 
        # the existing numbers
595
 
        self.assertSortAndIterate(
596
 
            {'A': [],
597
 
             'B': ['A'],
598
 
             'C': ['A'],
599
 
             'D': ['B'],
600
 
             'E': ['C'],
601
 
             'F': ['C'],
602
 
             'G': ['D', 'E'],
603
 
             'H': ['F'],
604
 
             'I': ['F'],
605
 
             'J': ['G', 'H'],
606
 
             'K': ['I'],
607
 
             'L': ['J', 'K'],
608
 
             'M': ['A'],
609
 
             'N': ['L', 'M'],
610
 
            },
611
 
            'N',
612
 
            [('N', 0, (7,), False),
613
 
             ('M', 1, (1,4,1), True),
614
 
             ('L', 0, (6,), False),
615
 
             ('K', 1, (1,3,2), False),
616
 
             ('I', 1, (1,3,1), True),
617
 
             ('J', 0, (5,), False),
618
 
             ('H', 1, (1,2,2), False),
619
 
             ('F', 1, (1,2,1), True),
620
 
             ('G', 0, (4,), False),
621
 
             ('E', 1, (1,1,2), False),
622
 
             ('C', 1, (1,1,1), True),
623
 
             ('D', 0, (3,), False),
624
 
             ('B', 0, (2,), False),
625
 
             ('A', 0, (1,),  True),
626
 
             ],
627
 
            )
628
 
 
629
 
    def test_end_of_merge_not_last_revision_in_branch(self):
630
 
        # within a branch only the last revision gets an
631
 
        # end of merge marker.
632
 
        self.assertSortAndIterate(
633
 
            {'A': ['B'],
634
 
             'B': [],
635
 
             },
636
 
            'A',
637
 
            [('A', 0, (2,), False),
638
 
             ('B', 0, (1,), True)
639
 
             ],
640
 
            )
641
 
 
642
 
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
643
 
        # when multiple branches are merged at once, both of their
644
 
        # branch-endpoints should be listed as end-of-merge.
645
 
        # Also, the order of the multiple merges should be
646
 
        # left-right shown top to bottom.
647
 
        # * means end of merge
648
 
        # A 0    [H, B, E]
649
 
        # B  1   [D, C]
650
 
        # C   2  [D]       *
651
 
        # D  1   [H]       *
652
 
        # E  1   [G, F]
653
 
        # F   2  [G]       *
654
 
        # G  1   [H]       *
655
 
        # H 0    []        *
656
 
        self.assertSortAndIterate(
657
 
            {'A': ['H', 'B', 'E'],
658
 
             'B': ['D', 'C'],
659
 
             'C': ['D'],
660
 
             'D': ['H'],
661
 
             'E': ['G', 'F'],
662
 
             'F': ['G'],
663
 
             'G': ['H'],
664
 
             'H': [],
665
 
             },
666
 
            'A',
667
 
            [('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),
674
 
             ('H', 0, (1,), True),
675
 
             ],
676
 
            )
677
 
 
678
 
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
679
 
        """When there are parallel roots, check their revnos."""
680
 
        self.assertSortAndIterate(
681
 
            {'A': [],
682
 
             'B': [],
683
 
             'C': ['A', 'B']},
684
 
            'C',
685
 
            [('C', 0, (2,), False),
686
 
             ('B', 1, (0,1,1), True),
687
 
             ('A', 0, (1,), True),
688
 
             ],
689
 
            )
690
 
 
691
 
    def test_revnos_are_globally_assigned(self):
692
 
        """revnos are assigned according to the revision they derive from."""
693
 
        # in this test we setup a number of branches that all derive from
694
 
        # the first revision, and then merge them one at a time, which
695
 
        # should give the revisions as they merge numbers still deriving from
696
 
        # the revision were based on.
697
 
        # merge 3: J: ['G', 'I']
698
 
        # branch 3:
699
 
        #  I: ['H']
700
 
        #  H: ['A']
701
 
        # merge 2: G: ['D', 'F']
702
 
        # branch 2:
703
 
        #  F: ['E']
704
 
        #  E: ['A']
705
 
        # merge 1: D: ['A', 'C']
706
 
        # branch 1:
707
 
        #  C: ['B']
708
 
        #  B: ['A']
709
 
        # root: A: []
710
 
        self.assertSortAndIterate(
711
 
            {'J': ['G', 'I'],
712
 
             'I': ['H',],
713
 
             'H': ['A'],
714
 
             'G': ['D', 'F'],
715
 
             'F': ['E'],
716
 
             'E': ['A'],
717
 
             'D': ['A', 'C'],
718
 
             'C': ['B'],
719
 
             'B': ['A'],
720
 
             'A': [],
721
 
             },
722
 
            'J',
723
 
            [('J', 0, (4,), False),
724
 
             ('I', 1, (1,3,2), False),
725
 
             ('H', 1, (1,3,1), True),
726
 
             ('G', 0, (3,), False),
727
 
             ('F', 1, (1,2,2), False),
728
 
             ('E', 1, (1,2,1), True),
729
 
             ('D', 0, (2,), False),
730
 
             ('C', 1, (1,1,2), False),
731
 
             ('B', 1, (1,1,1), True),
732
 
             ('A', 0, (1,), True),
733
 
             ],
734
 
            )
735
 
 
736
 
    def test_roots_and_sub_branches_versus_ghosts(self):
737
 
        """Extra roots and their mini branches use the same numbering.
738
 
 
739
 
        All of them use the 0-node numbering.
740
 
        """
741
 
        #       A D   K
742
 
        #       | |\  |\
743
 
        #       B E F L M
744
 
        #       | |/  |/
745
 
        #       C G   N
746
 
        #       |/    |\
747
 
        #       H I   O P
748
 
        #       |/    |/
749
 
        #       J     Q
750
 
        #       |.---'
751
 
        #       R
752
 
        self.assertSortAndIterate(
753
 
            {'A': [],
754
 
             'B': ['A'],
755
 
             'C': ['B'],
756
 
             'D': [],
757
 
             'E': ['D'],
758
 
             'F': ['D'],
759
 
             'G': ['E', 'F'],
760
 
             'H': ['C', 'G'],
761
 
             'I': [],
762
 
             'J': ['H', 'I'],
763
 
             'K': [],
764
 
             'L': ['K'],
765
 
             'M': ['K'],
766
 
             'N': ['L', 'M'],
767
 
             'O': ['N'],
768
 
             'P': ['N'],
769
 
             'Q': ['O', 'P'],
770
 
             'R': ['J', 'Q'],
771
 
            },
772
 
            'R',
773
 
            [('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),
781
 
             ('J', 0, (5,), False),
782
 
             ('I', 1, (0,3,1), True),
783
 
             ('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),
788
 
             ('C', 0, (3,), False),
789
 
             ('B', 0, (2,), False),
790
 
             ('A', 0, (1,), True),
791
 
             ],
792
 
            )
793
 
 
794
 
    def test_ghost(self):
795
 
        # merge_sort should be able to ignore ghosts
796
 
        # A
797
 
        # |
798
 
        # B ghost
799
 
        # |/
800
 
        # C
801
 
        self.assertSortAndIterate(
802
 
            {'A': [],
803
 
             'B': ['A'],
804
 
             'C': ['B', 'ghost'],
805
 
            },
806
 
            'C',
807
 
            [('C', 0, (3,), False),
808
 
             ('B', 0, (2,), False),
809
 
             ('A', 0, (1,), True),
810
 
            ])
811
 
 
812
 
    def test_lefthand_ghost(self):
813
 
        # ghost
814
 
        #  |
815
 
        #  A
816
 
        #  |
817
 
        #  B
818
 
        self.assertSortAndIterate(
819
 
            {'A': ['ghost'],
820
 
             'B': ['A'],
821
 
            }, 'B',
822
 
            [('B', 0, (2,), False),
823
 
             ('A', 0, (1,), True),
824
 
            ])
825
 
 
826
 
    def test_graph_cycle(self):
827
 
        # merge_sort should fail with a simple error when a graph cycle is
828
 
        # encountered.
829
 
        #
830
 
        # A
831
 
        # |,-.
832
 
        # B  |
833
 
        # |  |
834
 
        # C  ^
835
 
        # |  |
836
 
        # D  |
837
 
        # |'-'
838
 
        # E
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
 
                [])
849
 
 
850
 
 
851
 
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
852
 
    """Test the sort order returned by gc_sort."""
853
 
 
854
 
    def assertSorted(self, expected, parent_map):
855
 
        graph = self.make_known_graph(parent_map)
856
 
        value = graph.gc_sort()
857
 
        if expected != value:
858
 
            self.assertEqualDiff(pprint.pformat(expected),
859
 
                                 pprint.pformat(value))
860
 
 
861
 
    def test_empty(self):
862
 
        self.assertSorted([], {})
863
 
 
864
 
    def test_single(self):
865
 
        self.assertSorted(['a'], {'a':()})
866
 
        self.assertSorted([('a',)], {('a',):()})
867
 
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
868
 
 
869
 
    def test_linear(self):
870
 
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
871
 
        self.assertSorted([('c',), ('b',), ('a',)],
872
 
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
873
 
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
874
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
875
 
                           ('F', 'c'): (('F', 'b'),)})
876
 
 
877
 
    def test_mixed_ancestries(self):
878
 
        # Each prefix should be sorted separately
879
 
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
880
 
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
881
 
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
882
 
                          ],
883
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
884
 
                           ('F', 'c'): (('F', 'b'),),
885
 
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
886
 
                           ('G', 'c'): (('G', 'b'),),
887
 
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
888
 
                           ('Q', 'c'): (('Q', 'b'),),
889
 
                          })
890
 
 
891
 
    def test_stable_sorting(self):
892
 
        # the sort order should be stable even when extra nodes are added
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',)})
899
 
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
900
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
901
 
                           'Z':('a',)})
902
 
        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'),
907
 
                           })
908
 
 
909
 
    def test_skip_ghost(self):
910
 
        self.assertSorted(['b', 'c', 'a'],
911
 
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
912
 
 
913
 
    def test_skip_mainline_ghost(self):
914
 
        self.assertSorted(['b', 'c', 'a'],
915
 
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})