/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/tests/test__known_graph.py

  • Committer: Breezy landing bot
  • Author(s): Jelmer Vernooij
  • Date: 2018-03-25 11:54:30 UTC
  • mfrom: (6855.4.10 more-bees)
  • Revision ID: breezy.the.bot@gmail.com-20180325115430-75xnlbrmzjoomd83
Add more bees. In particular:

* for file ids
* for revision ids
* for file contents in build_tree_contents()

Merged from https://code.launchpad.net/~jelmer/brz/more-bees/+merge/337919

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test__known_graph.py
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2009, 2010, 2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
18
18
 
19
19
import pprint
20
20
 
21
 
from bzrlib import (
 
21
from .. import (
22
22
    errors,
23
 
    graph as _mod_graph,
24
23
    _known_graph_py,
25
24
    tests,
26
25
    )
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."""
 
26
from . import test_graph
 
27
from ..revision import NULL_REVISION
 
28
from .scenarios import load_tests_apply_scenarios
 
29
from . import (
 
30
    features,
 
31
    )
 
32
 
 
33
 
 
34
def caching_scenarios():
33
35
    scenarios = [
34
36
        ('python', {'module': _known_graph_py, 'do_cache': True}),
35
37
    ]
36
 
    caching_scenarios = [
37
 
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
38
 
    ]
39
 
    suite = loader.suiteClass()
40
38
    if compiled_known_graph_feature.available():
41
39
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
42
40
                                'do_cache': True}))
43
 
        caching_scenarios.append(
 
41
    return scenarios
 
42
 
 
43
 
 
44
def non_caching_scenarios():
 
45
    scenarios = [
 
46
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
47
    ]
 
48
    if compiled_known_graph_feature.available():
 
49
        scenarios.append(
44
50
            ('C-nocache', {'module': compiled_known_graph_feature.module,
45
51
                           '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_feature)
51
 
        suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
52
 
    # TestKnownGraphHeads needs to be permutated with and without caching.
53
 
    # All other TestKnownGraph tests only need to be tested across module
54
 
    heads_suite, other_suite = tests.split_suite_by_condition(
55
 
        standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
56
 
    suite = tests.multiply_tests(other_suite, scenarios, suite)
57
 
    suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
58
 
                                 suite)
59
 
    return suite
60
 
 
61
 
 
62
 
compiled_known_graph_feature = tests.ModuleAvailableFeature(
63
 
                                    'bzrlib._known_graph_pyx')
 
52
    return scenarios
 
53
 
 
54
 
 
55
load_tests = load_tests_apply_scenarios
 
56
 
 
57
 
 
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
 
59
    'breezy._known_graph_pyx')
64
60
 
65
61
 
66
62
#  a
75
71
 
76
72
class TestCaseWithKnownGraph(tests.TestCase):
77
73
 
 
74
    scenarios = caching_scenarios()
78
75
    module = None # Set by load_tests
79
76
 
80
77
    def make_known_graph(self, ancestry):
214
211
 
215
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
216
213
 
 
214
    scenarios = caching_scenarios() + non_caching_scenarios()
217
215
    do_cache = None # Set by load_tests
218
216
 
219
217
    def test_heads_null(self):
220
218
        graph = self.make_known_graph(test_graph.ancestry_1)
221
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
222
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
223
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
224
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
225
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
219
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
220
        self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
 
221
        self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
 
222
        self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
 
223
        self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
226
224
 
227
225
    def test_heads_one(self):
228
226
        # A single node will always be a head
229
227
        graph = self.make_known_graph(test_graph.ancestry_1)
230
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
231
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
232
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
233
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
234
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
235
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
228
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
229
        self.assertEqual({'rev1'}, graph.heads(['rev1']))
 
230
        self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
 
231
        self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
 
232
        self.assertEqual({'rev3'}, graph.heads(['rev3']))
 
233
        self.assertEqual({'rev4'}, graph.heads(['rev4']))
236
234
 
237
235
    def test_heads_single(self):
238
236
        graph = self.make_known_graph(test_graph.ancestry_1)
239
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
240
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
241
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
242
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
243
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
244
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
245
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
246
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
247
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
237
        self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
 
238
        self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
 
239
        self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
 
240
        self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
 
241
        self.assertEqual({'rev3'}, graph.heads(['rev3', 'rev2a']))
 
242
        self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
 
243
        self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
 
244
        self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
 
245
        self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
248
246
 
249
247
    def test_heads_two_heads(self):
250
248
        graph = self.make_known_graph(test_graph.ancestry_1)
251
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
249
        self.assertEqual({'rev2a', 'rev2b'},
252
250
                         graph.heads(['rev2a', 'rev2b']))
253
 
        self.assertEqual(set(['rev3', 'rev2b']),
 
251
        self.assertEqual({'rev3', 'rev2b'},
254
252
                         graph.heads(['rev3', 'rev2b']))
255
253
 
256
254
    def test_heads_criss_cross(self):
257
255
        graph = self.make_known_graph(test_graph.criss_cross)
258
 
        self.assertEqual(set(['rev2a']),
 
256
        self.assertEqual({'rev2a'},
259
257
                         graph.heads(['rev2a', 'rev1']))
260
 
        self.assertEqual(set(['rev2b']),
 
258
        self.assertEqual({'rev2b'},
261
259
                         graph.heads(['rev2b', 'rev1']))
262
 
        self.assertEqual(set(['rev3a']),
 
260
        self.assertEqual({'rev3a'},
263
261
                         graph.heads(['rev3a', 'rev1']))
264
 
        self.assertEqual(set(['rev3b']),
 
262
        self.assertEqual({'rev3b'},
265
263
                         graph.heads(['rev3b', 'rev1']))
266
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
264
        self.assertEqual({'rev2a', 'rev2b'},
267
265
                         graph.heads(['rev2a', 'rev2b']))
268
 
        self.assertEqual(set(['rev3a']),
 
266
        self.assertEqual({'rev3a'},
269
267
                         graph.heads(['rev3a', 'rev2a']))
270
 
        self.assertEqual(set(['rev3a']),
 
268
        self.assertEqual({'rev3a'},
271
269
                         graph.heads(['rev3a', 'rev2b']))
272
 
        self.assertEqual(set(['rev3a']),
 
270
        self.assertEqual({'rev3a'},
273
271
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
274
 
        self.assertEqual(set(['rev3b']),
 
272
        self.assertEqual({'rev3b'},
275
273
                         graph.heads(['rev3b', 'rev2a']))
276
 
        self.assertEqual(set(['rev3b']),
 
274
        self.assertEqual({'rev3b'},
277
275
                         graph.heads(['rev3b', 'rev2b']))
278
 
        self.assertEqual(set(['rev3b']),
 
276
        self.assertEqual({'rev3b'},
279
277
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
280
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
278
        self.assertEqual({'rev3a', 'rev3b'},
281
279
                         graph.heads(['rev3a', 'rev3b']))
282
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
280
        self.assertEqual({'rev3a', 'rev3b'},
283
281
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
284
282
 
285
283
    def test_heads_shortcut(self):
286
284
        graph = self.make_known_graph(test_graph.history_shortcut)
287
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
285
        self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
288
286
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
289
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
287
        self.assertEqual({'rev3a', 'rev3b'},
290
288
                         graph.heads(['rev3a', 'rev3b']))
291
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
289
        self.assertEqual({'rev3a', 'rev3b'},
292
290
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
293
 
        self.assertEqual(set(['rev2a', 'rev3b']),
 
291
        self.assertEqual({'rev2a', 'rev3b'},
294
292
                         graph.heads(['rev2a', 'rev3b']))
295
 
        self.assertEqual(set(['rev2c', 'rev3a']),
 
293
        self.assertEqual({'rev2c', 'rev3a'},
296
294
                         graph.heads(['rev2c', 'rev3a']))
297
295
 
298
296
    def test_heads_linear(self):
299
297
        graph = self.make_known_graph(test_graph.racing_shortcuts)
300
 
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
301
 
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
302
 
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
303
 
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
298
        self.assertEqual({'w'}, graph.heads(['w', 's']))
 
299
        self.assertEqual({'z'}, graph.heads(['w', 's', 'z']))
 
300
        self.assertEqual({'w', 'q'}, graph.heads(['w', 's', 'q']))
 
301
        self.assertEqual({'z'}, graph.heads(['s', 'z']))
304
302
 
305
303
    def test_heads_alt_merge(self):
306
304
        graph = self.make_known_graph(alt_merge)
307
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
 
305
        self.assertEqual({'c'}, graph.heads(['a', 'c']))
308
306
 
309
307
    def test_heads_with_ghost(self):
310
308
        graph = self.make_known_graph(test_graph.with_ghost)
311
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
312
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
313
 
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
314
 
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
315
 
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
316
 
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
317
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
318
 
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
 
309
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
 
310
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c']))
 
311
        self.assertEqual({'a', 'g'}, graph.heads(['a', 'g']))
 
312
        self.assertEqual({'f', 'g'}, graph.heads(['f', 'g']))
 
313
        self.assertEqual({'c'}, graph.heads(['c', 'g']))
 
314
        self.assertEqual({'c'}, graph.heads(['c', 'b', 'd', 'g']))
 
315
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'e', 'g']))
 
316
        self.assertEqual({'a', 'c'}, graph.heads(['a', 'c', 'f']))
319
317
 
320
318
    def test_filling_in_ghosts_resets_head_cache(self):
321
319
        graph = self.make_known_graph(test_graph.with_ghost)
322
 
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
320
        self.assertEqual({'e', 'g'}, graph.heads(['e', 'g']))
323
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
324
322
        # different
325
323
        graph.add_node('g', ['e'])
326
 
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
 
324
        self.assertEqual({'g'}, graph.heads(['e', 'g']))
327
325
 
328
326
 
329
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
464
462
             'C': ['A', 'B']},
465
463
            'C',
466
464
            [('C', 0, (2,), False),
467
 
             ('B', 1, (1,1,1), True),
 
465
             ('B', 1, (1, 1, 1), True),
468
466
             ('A', 0, (1,), True),
469
467
             ],
470
468
            )
487
485
                 }
488
486
        self.assertSortAndIterate(graph, 'F',
489
487
            [('F', 0, (3,), False),
490
 
             ('D', 1, (2,2,1), False),
491
 
             ('C', 2, (2,1,1), True),
 
488
             ('D', 1, (2, 2, 1), False),
 
489
             ('C', 2, (2, 1, 1), True),
492
490
             ('B', 0, (2,), False),
493
491
             ('A', 0, (1,), True),
494
492
             ])
510
508
                 }
511
509
        self.assertSortAndIterate(graph, 'F',
512
510
            [('F', 0, (3,), False),
513
 
             ('D', 1, (2,1,2), False),
514
 
             ('C', 2, (2,2,1), True),
515
 
             ('X', 1, (2,1,1), True),
 
511
             ('D', 1, (2, 1, 2), False),
 
512
             ('C', 2, (2, 2, 1), True),
 
513
             ('X', 1, (2, 1, 1), True),
516
514
             ('B', 0, (2,), False),
517
515
             ('A', 0, (1,), True),
518
516
             ])
541
539
             },
542
540
            'A',
543
541
            [('A', 0, (3,),  False),
544
 
             ('B', 1, (1,3,2), False),
545
 
             ('C', 1, (1,3,1), True),
 
542
             ('B', 1, (1, 3, 2), False),
 
543
             ('C', 1, (1, 3, 1), True),
546
544
             ('D', 0, (2,), False),
547
 
             ('E', 1, (1,1,2), False),
548
 
             ('F', 2, (1,2,1), True),
549
 
             ('G', 1, (1,1,1), True),
 
545
             ('E', 1, (1, 1, 2), False),
 
546
             ('F', 2, (1, 2, 1), True),
 
547
             ('G', 1, (1, 1, 1), True),
550
548
             ('H', 0, (1,), True),
551
549
             ],
552
550
            )
579
577
            },
580
578
            'L',
581
579
            [('L', 0, (6,), False),
582
 
             ('K', 1, (1,3,2), False),
583
 
             ('I', 1, (1,3,1), True),
 
580
             ('K', 1, (1, 3, 2), False),
 
581
             ('I', 1, (1, 3, 1), True),
584
582
             ('J', 0, (5,), False),
585
 
             ('H', 1, (1,2,2), False),
586
 
             ('F', 1, (1,2,1), True),
 
583
             ('H', 1, (1, 2, 2), False),
 
584
             ('F', 1, (1, 2, 1), True),
587
585
             ('G', 0, (4,), False),
588
 
             ('E', 1, (1,1,2), False),
589
 
             ('C', 1, (1,1,1), True),
 
586
             ('E', 1, (1, 1, 2), False),
 
587
             ('C', 1, (1, 1, 1), True),
590
588
             ('D', 0, (3,), False),
591
589
             ('B', 0, (2,), False),
592
590
             ('A', 0, (1,),  True),
612
610
            },
613
611
            'N',
614
612
            [('N', 0, (7,), False),
615
 
             ('M', 1, (1,4,1), True),
 
613
             ('M', 1, (1, 4, 1), True),
616
614
             ('L', 0, (6,), False),
617
 
             ('K', 1, (1,3,2), False),
618
 
             ('I', 1, (1,3,1), True),
 
615
             ('K', 1, (1, 3, 2), False),
 
616
             ('I', 1, (1, 3, 1), True),
619
617
             ('J', 0, (5,), False),
620
 
             ('H', 1, (1,2,2), False),
621
 
             ('F', 1, (1,2,1), True),
 
618
             ('H', 1, (1, 2, 2), False),
 
619
             ('F', 1, (1, 2, 1), True),
622
620
             ('G', 0, (4,), False),
623
 
             ('E', 1, (1,1,2), False),
624
 
             ('C', 1, (1,1,1), True),
 
621
             ('E', 1, (1, 1, 2), False),
 
622
             ('C', 1, (1, 1, 1), True),
625
623
             ('D', 0, (3,), False),
626
624
             ('B', 0, (2,), False),
627
625
             ('A', 0, (1,),  True),
667
665
             },
668
666
            'A',
669
667
            [('A', 0, (2,), False),
670
 
             ('B', 1, (1,3,2), False),
671
 
             ('C', 2, (1,4,1), True),
672
 
             ('D', 1, (1,3,1), True),
673
 
             ('E', 1, (1,1,2), False),
674
 
             ('F', 2, (1,2,1), True),
675
 
             ('G', 1, (1,1,1), True),
 
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),
676
674
             ('H', 0, (1,), True),
677
675
             ],
678
676
            )
685
683
             'C': ['A', 'B']},
686
684
            'C',
687
685
            [('C', 0, (2,), False),
688
 
             ('B', 1, (0,1,1), True),
 
686
             ('B', 1, (0, 1, 1), True),
689
687
             ('A', 0, (1,), True),
690
688
             ],
691
689
            )
723
721
             },
724
722
            'J',
725
723
            [('J', 0, (4,), False),
726
 
             ('I', 1, (1,3,2), False),
727
 
             ('H', 1, (1,3,1), True),
 
724
             ('I', 1, (1, 3, 2), False),
 
725
             ('H', 1, (1, 3, 1), True),
728
726
             ('G', 0, (3,), False),
729
 
             ('F', 1, (1,2,2), False),
730
 
             ('E', 1, (1,2,1), True),
 
727
             ('F', 1, (1, 2, 2), False),
 
728
             ('E', 1, (1, 2, 1), True),
731
729
             ('D', 0, (2,), False),
732
 
             ('C', 1, (1,1,2), False),
733
 
             ('B', 1, (1,1,1), True),
 
730
             ('C', 1, (1, 1, 2), False),
 
731
             ('B', 1, (1, 1, 1), True),
734
732
             ('A', 0, (1,), True),
735
733
             ],
736
734
            )
773
771
            },
774
772
            'R',
775
773
            [('R', 0, (6,), False),
776
 
             ('Q', 1, (0,4,5), False),
777
 
             ('P', 2, (0,6,1), True),
778
 
             ('O', 1, (0,4,4), False),
779
 
             ('N', 1, (0,4,3), False),
780
 
             ('M', 2, (0,5,1), True),
781
 
             ('L', 1, (0,4,2), False),
782
 
             ('K', 1, (0,4,1), True),
 
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),
783
781
             ('J', 0, (5,), False),
784
 
             ('I', 1, (0,3,1), True),
 
782
             ('I', 1, (0, 3, 1), True),
785
783
             ('H', 0, (4,), False),
786
 
             ('G', 1, (0,1,3), False),
787
 
             ('F', 2, (0,2,1), True),
788
 
             ('E', 1, (0,1,2), False),
789
 
             ('D', 1, (0,1,1), True),
 
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),
790
788
             ('C', 0, (3,), False),
791
789
             ('B', 0, (2,), False),
792
790
             ('A', 0, (1,), True),
882
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
883
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
884
882
                          ],
885
 
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
883
                          {('F', 'a'): (), ('F', 'b'): (('F', 'a'),),
886
884
                           ('F', 'c'): (('F', 'b'),),
887
 
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
885
                           ('G', 'a'): (), ('G', 'b'): (('G', 'a'),),
888
886
                           ('G', 'c'): (('G', 'b'),),
889
 
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
887
                           ('Q', 'a'): (), ('Q', 'b'): (('Q', 'a'),),
890
888
                           ('Q', 'c'): (('Q', 'b'),),
891
889
                          })
892
890
 
902
900
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
903
901
                           'Z':('a',)})
904
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
905
 
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
906
 
                           'Z':('a',),
907
 
                           'e':('b', 'c', 'd'),
908
 
                           'f':('d', 'Z'),
 
903
                          {'a': (), 'b': ('a',), 'c': ('a',), 'd': ('a',),
 
904
                           'Z': ('a',),
 
905
                           'e': ('b', 'c', 'd'),
 
906
                           'f': ('d', 'Z'),
909
907
                           })
910
908
 
911
909
    def test_skip_ghost(self):