~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: Andrew Bennetts
  • Date: 2009-08-07 04:17:51 UTC
  • mto: This revision was merged to the branch mainline in revision 4608.
  • Revision ID: andrew.bennetts@canonical.com-20090807041751-0vhb0y0g7k49hr45
Review comments from John.

Show diffs side-by-side

added added

removed removed

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