← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

  • Committer: Alexander Belchenko
  • Date: 2006-07-30 16:43:12 UTC
  • mto: (1711.2.111 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1906.
  • Revision ID: bialix@ukr.net-20060730164312-b025fd3ff0cee59e
rename  gpl.txt => COPYING.txt

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
1
 
# Copyright (C) 2005 Canonical Ltd
 
1
# Copyright (C) 2005 by 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
18
"""Tests for topological sort."""
19
19
 
20
 
import pprint
21
20
 
22
21
from bzrlib.tests import TestCase
23
22
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
24
23
from bzrlib.errors import GraphCycleError
25
 
from bzrlib.revision import NULL_REVISION
26
24
 
27
25
 
28
26
class TopoSortTests(TestCase):
40
38
                          list,
41
39
                          TopoSorter(graph).iter_topo_order())
42
40
 
43
 
    def assertSortAndIterateOrder(self, graph):
44
 
        """Check topo_sort and iter_topo_order is genuinely topological order.
45
 
 
46
 
        For every child in the graph, check if it comes after all of it's
47
 
        parents.
48
 
        """
49
 
        sort_result = topo_sort(graph)
50
 
        iter_result = list(TopoSorter(graph).iter_topo_order())
51
 
        for (node, parents) in graph:
52
 
            for parent in parents:
53
 
                if sort_result.index(node) < sort_result.index(parent):
54
 
                    self.fail("parent %s must come before child %s:\n%s"
55
 
                              % (parent, node, sort_result))
56
 
                if iter_result.index(node) < iter_result.index(parent):
57
 
                    self.fail("parent %s must come before child %s:\n%s"
58
 
                              % (parent, node, iter_result))
59
 
 
60
41
    def test_tsort_empty(self):
61
42
        """TopoSort empty list"""
62
43
        self.assertSortAndIterate([], [])
68
49
    def test_tsort_cycle(self):
69
50
        """TopoSort traps graph with cycles"""
70
51
        self.assertSortAndIterateRaise(GraphCycleError,
71
 
                                       {0: [1],
 
52
                                       {0: [1], 
72
53
                                        1: [0]}.items())
73
54
 
74
55
    def test_tsort_cycle_2(self):
75
56
        """TopoSort traps graph with longer cycle"""
76
57
        self.assertSortAndIterateRaise(GraphCycleError,
77
 
                                       {0: [1],
78
 
                                        1: [2],
 
58
                                       {0: [1], 
 
59
                                        1: [2], 
79
60
                                        2: [0]}.items())
80
 
 
81
 
    def test_topo_sort_cycle_with_tail(self):
82
 
        """TopoSort traps graph with longer cycle"""
83
 
        self.assertSortAndIterateRaise(GraphCycleError,
84
 
                                       {0: [1],
85
 
                                        1: [2],
86
 
                                        2: [3, 4],
87
 
                                        3: [0],
88
 
                                        4: []}.items())
89
 
 
 
61
                 
90
62
    def test_tsort_1(self):
91
63
        """TopoSort simple nontrivial graph"""
92
 
        self.assertSortAndIterate({0: [3],
 
64
        self.assertSortAndIterate({0: [3], 
93
65
                                   1: [4],
94
66
                                   2: [1, 4],
95
 
                                   3: [],
 
67
                                   3: [], 
96
68
                                   4: [0, 3]}.items(),
97
69
                                  [3, 0, 4, 1, 2])
98
70
 
99
71
    def test_tsort_partial(self):
100
72
        """Topological sort with partial ordering.
101
73
 
102
 
        Multiple correct orderings are possible, so test for 
103
 
        correctness, not for exact match on the resulting list.
 
74
        If the graph does not give an order between two nodes, they are 
 
75
        returned in lexicographical order.
104
76
        """
105
 
        self.assertSortAndIterateOrder([(0, []),
 
77
        self.assertSortAndIterate(([(0, []),
106
78
                                   (1, [0]),
107
79
                                   (2, [0]),
108
80
                                   (3, [0]),
110
82
                                   (5, [1, 2]),
111
83
                                   (6, [1, 2]),
112
84
                                   (7, [2, 3]),
113
 
                                   (8, [0, 1, 4, 5, 6])])
114
 
 
115
 
    def test_tsort_unincluded_parent(self):
116
 
        """Sort nodes, but don't include some parents in the output"""
117
 
        self.assertSortAndIterate([(0, [1]),
118
 
                                   (1, [2])],
119
 
                                   [1, 0])
 
85
                                   (8, [0, 1, 4, 5, 6])]),
 
86
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
120
87
 
121
88
 
122
89
class MergeSortTests(TestCase):
123
90
 
124
91
    def assertSortAndIterate(self, graph, branch_tip, result_list,
125
 
            generate_revno, mainline_revisions=None):
 
92
            mainline_revisions=None):
126
93
        """Check that merge based sorting and iter_topo_order on graph works."""
127
 
        value = merge_sort(graph, branch_tip,
128
 
                           mainline_revisions=mainline_revisions,
129
 
                           generate_revno=generate_revno)
130
 
        if result_list != value:
131
 
            self.assertEqualDiff(pprint.pformat(result_list),
132
 
                                 pprint.pformat(value))
 
94
        self.assertEquals(result_list,
 
95
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
133
96
        self.assertEqual(result_list,
134
97
            list(MergeSorter(
135
98
                graph,
136
99
                branch_tip,
137
 
                mainline_revisions=mainline_revisions,
138
 
                generate_revno=generate_revno,
139
 
                ).iter_topo_order()))
 
100
                mainline_revisions=mainline_revisions).iter_topo_order()))
140
101
 
141
102
    def test_merge_sort_empty(self):
142
103
        # sorting of an emptygraph does not error
143
 
        self.assertSortAndIterate({}, None, [], False)
144
 
        self.assertSortAndIterate({}, None, [], True)
145
 
        self.assertSortAndIterate({}, NULL_REVISION, [], False)
146
 
        self.assertSortAndIterate({}, NULL_REVISION, [], True)
 
104
        self.assertSortAndIterate({}, None, [])
147
105
 
148
106
    def test_merge_sort_not_empty_no_tip(self):
149
107
        # merge sorting of a branch starting with None should result
150
108
        # in an empty list: no revisions are dragged in.
151
 
        self.assertSortAndIterate({0: []}.items(), None, [], False)
152
 
        self.assertSortAndIterate({0: []}.items(), None, [], True)
 
109
        self.assertSortAndIterate({0: []}.items(), None, [])
153
110
 
154
111
    def test_merge_sort_one_revision(self):
155
112
        # sorting with one revision as the tip returns the correct fields:
156
113
        # sequence - 0, revision id, merge depth - 0, end_of_merge
157
114
        self.assertSortAndIterate({'id': []}.items(),
158
115
                                  'id',
159
 
                                  [(0, 'id', 0, True)],
160
 
                                  False)
161
 
        self.assertSortAndIterate({'id': []}.items(),
162
 
                                  'id',
163
 
                                  [(0, 'id', 0, (1,), True)],
164
 
                                  True)
165
 
 
 
116
                                  [(0, 'id', 0, True)])
 
117
    
166
118
    def test_sequence_numbers_increase_no_merges(self):
167
119
        # emit a few revisions with no merges to check the sequence
168
120
        # numbering works in trivial cases
174
126
            [(0, 'C', 0, False),
175
127
             (1, 'B', 0, False),
176
128
             (2, 'A', 0, True),
177
 
             ],
178
 
            False
179
 
            )
180
 
        self.assertSortAndIterate(
181
 
            {'A': [],
182
 
             'B': ['A'],
183
 
             'C': ['B']}.items(),
184
 
            'C',
185
 
            [(0, 'C', 0, (3,), False),
186
 
             (1, 'B', 0, (2,), False),
187
 
             (2, 'A', 0, (1,), True),
188
 
             ],
189
 
            True
 
129
             ]
190
130
            )
191
131
 
192
132
    def test_sequence_numbers_increase_with_merges(self):
199
139
            [(0, 'C', 0, False),
200
140
             (1, 'B', 1, True),
201
141
             (2, 'A', 0, True),
202
 
             ],
203
 
            False
204
 
            )
205
 
        self.assertSortAndIterate(
206
 
            {'A': [],
207
 
             'B': ['A'],
208
 
             'C': ['A', 'B']}.items(),
209
 
            'C',
210
 
            [(0, 'C', 0, (2,), False),
211
 
             (1, 'B', 1, (1,1,1), True),
212
 
             (2, 'A', 0, (1,), True),
213
 
             ],
214
 
            True
215
 
            )
216
 
 
217
 
    def test_merge_sort_race(self):
218
 
        # A
219
 
        # |
220
 
        # B-.
221
 
        # |\ \
222
 
        # | | C
223
 
        # | |/
224
 
        # | D
225
 
        # |/
226
 
        # F
227
 
        graph = {'A': [],
228
 
                 'B': ['A'],
229
 
                 'C': ['B'],
230
 
                 'D': ['B', 'C'],
231
 
                 'F': ['B', 'D'],
232
 
                 }
233
 
        self.assertSortAndIterate(graph, 'F',
234
 
            [(0, 'F', 0, (3,), False),
235
 
             (1, 'D', 1, (2,2,1), False),
236
 
             (2, 'C', 2, (2,1,1), True),
237
 
             (3, 'B', 0, (2,), False),
238
 
             (4, 'A', 0, (1,), True),
239
 
             ], True)
240
 
        # A
241
 
        # |
242
 
        # B-.
243
 
        # |\ \
244
 
        # | X C
245
 
        # | |/
246
 
        # | D
247
 
        # |/
248
 
        # F
249
 
        graph = {'A': [],
250
 
                 'B': ['A'],
251
 
                 'C': ['B'],
252
 
                 'X': ['B'],
253
 
                 'D': ['X', 'C'],
254
 
                 'F': ['B', 'D'],
255
 
                 }
256
 
        self.assertSortAndIterate(graph, 'F',
257
 
            [(0, 'F', 0, (3,), False),
258
 
             (1, 'D', 1, (2,1,2), False),
259
 
             (2, 'C', 2, (2,2,1), True),
260
 
             (3, 'X', 1, (2,1,1), True),
261
 
             (4, 'B', 0, (2,), False),
262
 
             (5, 'A', 0, (1,), True),
263
 
             ], True)
264
 
 
 
142
             ]
 
143
            )
 
144
        
265
145
    def test_merge_depth_with_nested_merges(self):
266
146
        # the merge depth marker should reflect the depth of the revision
267
147
        # in terms of merges out from the mainline
268
148
        # revid, depth, parents:
269
 
        #  A 0   [D, B]
270
 
        #  B  1  [C, F]
271
 
        #  C  1  [H]
 
149
        #  A 0   [D, B]   
 
150
        #  B  1  [C, F]   
 
151
        #  C  1  [H] 
272
152
        #  D 0   [H, E]
273
153
        #  E  1  [G, F]
274
154
        #  F   2 [G]
293
173
             (5, 'F', 2, True),
294
174
             (6, 'G', 1, True),
295
175
             (7, 'H', 0, True),
296
 
             ],
297
 
            False
298
 
            )
299
 
        self.assertSortAndIterate(
300
 
            {'A': ['D', 'B'],
301
 
             'B': ['C', 'F'],
302
 
             'C': ['H'],
303
 
             'D': ['H', 'E'],
304
 
             'E': ['G', 'F'],
305
 
             'F': ['G'],
306
 
             'G': ['H'],
307
 
             'H': []
308
 
             }.items(),
309
 
            'A',
310
 
            [(0, 'A', 0, (3,),  False),
311
 
             (1, 'B', 1, (1,3,2), False),
312
 
             (2, 'C', 1, (1,3,1), True),
313
 
             (3, 'D', 0, (2,), False),
314
 
             (4, 'E', 1, (1,1,2), False),
315
 
             (5, 'F', 2, (1,2,1), True),
316
 
             (6, 'G', 1, (1,1,1), True),
317
 
             (7, 'H', 0, (1,), True),
318
 
             ],
319
 
            True
320
 
            )
321
 
 
322
 
    def test_dotted_revnos_with_simple_merges(self):
323
 
        # A         1
324
 
        # |\
325
 
        # B C       2, 1.1.1
326
 
        # | |\
327
 
        # D E F     3, 1.1.2, 1.2.1
328
 
        # |/ /|
329
 
        # G H I     4, 1.2.2, 1.3.1
330
 
        # |/ /
331
 
        # J K       5, 1.3.2
332
 
        # |/
333
 
        # L         6
334
 
        self.assertSortAndIterate(
335
 
            {'A': [],
336
 
             'B': ['A'],
337
 
             'C': ['A'],
338
 
             'D': ['B'],
339
 
             'E': ['C'],
340
 
             'F': ['C'],
341
 
             'G': ['D', 'E'],
342
 
             'H': ['F'],
343
 
             'I': ['F'],
344
 
             'J': ['G', 'H'],
345
 
             'K': ['I'],
346
 
             'L': ['J', 'K'],
347
 
            }.items(),
348
 
            'L',
349
 
            [(0, 'L', 0, (6,), False),
350
 
             (1, 'K', 1, (1,3,2), False),
351
 
             (2, 'I', 1, (1,3,1), True),
352
 
             (3, 'J', 0, (5,), False),
353
 
             (4, 'H', 1, (1,2,2), False),
354
 
             (5, 'F', 1, (1,2,1), True),
355
 
             (6, 'G', 0, (4,), False),
356
 
             (7, 'E', 1, (1,1,2), False),
357
 
             (8, 'C', 1, (1,1,1), True),
358
 
             (9, 'D', 0, (3,), False),
359
 
             (10, 'B', 0, (2,), False),
360
 
             (11, 'A', 0, (1,),  True),
361
 
             ],
362
 
            True
363
 
            )
364
 
        # Adding a shortcut from the first revision should not change any of
365
 
        # the existing numbers
366
 
        self.assertSortAndIterate(
367
 
            {'A': [],
368
 
             'B': ['A'],
369
 
             'C': ['A'],
370
 
             'D': ['B'],
371
 
             'E': ['C'],
372
 
             'F': ['C'],
373
 
             'G': ['D', 'E'],
374
 
             'H': ['F'],
375
 
             'I': ['F'],
376
 
             'J': ['G', 'H'],
377
 
             'K': ['I'],
378
 
             'L': ['J', 'K'],
379
 
             'M': ['A'],
380
 
             'N': ['L', 'M'],
381
 
            }.items(),
382
 
            'N',
383
 
            [(0, 'N', 0, (7,), False),
384
 
             (1, 'M', 1, (1,4,1), True),
385
 
             (2, 'L', 0, (6,), False),
386
 
             (3, 'K', 1, (1,3,2), False),
387
 
             (4, 'I', 1, (1,3,1), True),
388
 
             (5, 'J', 0, (5,), False),
389
 
             (6, 'H', 1, (1,2,2), False),
390
 
             (7, 'F', 1, (1,2,1), True),
391
 
             (8, 'G', 0, (4,), False),
392
 
             (9, 'E', 1, (1,1,2), False),
393
 
             (10, 'C', 1, (1,1,1), True),
394
 
             (11, 'D', 0, (3,), False),
395
 
             (12, 'B', 0, (2,), False),
396
 
             (13, 'A', 0, (1,),  True),
397
 
             ],
398
 
            True
399
 
            )
400
 
 
 
176
             ]
 
177
            )
 
178
 
401
179
    def test_end_of_merge_not_last_revision_in_branch(self):
402
180
        # within a branch only the last revision gets an
403
181
        # end of merge marker.
408
186
            'A',
409
187
            [(0, 'A', 0, False),
410
188
             (1, 'B', 0, True)
411
 
             ],
412
 
            False
413
 
            )
414
 
        self.assertSortAndIterate(
415
 
            {'A': ['B'],
416
 
             'B': [],
417
 
             },
418
 
            'A',
419
 
            [(0, 'A', 0, (2,), False),
420
 
             (1, 'B', 0, (1,), True)
421
 
             ],
422
 
            True
 
189
             ]
423
190
            )
424
191
 
425
192
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
426
193
        # when multiple branches are merged at once, both of their
427
194
        # branch-endpoints should be listed as end-of-merge.
428
 
        # Also, the order of the multiple merges should be
 
195
        # Also, the order of the multiple merges should be 
429
196
        # left-right shown top to bottom.
430
197
        # * means end of merge
431
 
        # A 0    [H, B, E]
 
198
        # A 0    [H, B, E] 
432
199
        # B  1   [D, C]
433
200
        # C   2  [D]       *
434
201
        # D  1   [H]       *
455
222
             (5, 'F', 2, True),
456
223
             (6, 'G', 1, True),
457
224
             (7, 'H', 0, True),
458
 
             ],
459
 
            False
460
 
            )
461
 
        self.assertSortAndIterate(
462
 
            {'A': ['H', 'B', 'E'],
463
 
             'B': ['D', 'C'],
464
 
             'C': ['D'],
465
 
             'D': ['H'],
466
 
             'E': ['G', 'F'],
467
 
             'F': ['G'],
468
 
             'G': ['H'],
469
 
             'H': [],
470
 
             },
471
 
            'A',
472
 
            [(0, 'A', 0, (2,), False),
473
 
             (1, 'B', 1, (1,3,2), False),
474
 
             (2, 'C', 2, (1,4,1), True),
475
 
             (3, 'D', 1, (1,3,1), True),
476
 
             (4, 'E', 1, (1,1,2), False),
477
 
             (5, 'F', 2, (1,2,1), True),
478
 
             (6, 'G', 1, (1,1,1), True),
479
 
             (7, 'H', 0, (1,), True),
480
 
             ],
481
 
            True
 
225
             ]
482
226
            )
483
227
 
484
228
    def test_mainline_revs_partial(self):
505
249
        # and thus when truncated to D,B,A it should show
506
250
        # A 0
507
251
        # B 0
508
 
        # C 1
 
252
        # C 1 
509
253
        # because C is brought in by B in this view and D
510
254
        # is the terminating revision id
511
 
        # this should also preserve revision numbers: C should still be 2.1.1
512
255
        self.assertSortAndIterate(
513
256
            {'A': ['E', 'B'],
514
257
             'B': ['D', 'C'],
521
264
             (1, 'B', 0, False),
522
265
             (2, 'C', 1, True),
523
266
             ],
524
 
            False,
525
 
            mainline_revisions=['D', 'B', 'A']
526
 
            )
527
 
        self.assertSortAndIterate(
528
 
            {'A': ['E', 'B'],
529
 
             'B': ['D', 'C'],
530
 
             'C': ['D'],
531
 
             'D': ['E'],
532
 
             'E': []
533
 
             },
534
 
            'A',
535
 
            [(0, 'A', 0, (4,), False),
536
 
             (1, 'B', 0, (3,), False),
537
 
             (2, 'C', 1, (2,1,1), True),
538
 
             ],
539
 
            True,
540
267
            mainline_revisions=['D', 'B', 'A']
541
268
            )
542
269
 
549
276
            'A',
550
277
            [(0, 'A', 0, True),
551
278
             ],
552
 
            False,
553
 
            mainline_revisions=[None, 'A']
554
 
            )
555
 
        self.assertSortAndIterate(
556
 
            {'A': [],
557
 
             },
558
 
            'A',
559
 
            [(0, 'A', 0, (1,), True),
560
 
             ],
561
 
            True,
562
 
            mainline_revisions=[None, 'A']
563
 
            )
564
 
 
565
 
    def test_mainline_revs_with_ghost(self):
566
 
        # We have a mainline, but the end of it is actually a ghost
567
 
        # The graph that is passed to tsort has had ghosts filtered out, but
568
 
        # the mainline history has not.
569
 
        self.assertSortAndIterate(
570
 
            {'B':[],
571
 
             'C':['B']}.items(),
572
 
            'C',
573
 
            [(0, 'C', 0, (2,), False),
574
 
             (1, 'B', 0, (1,), True),
575
 
             ],
576
 
             True, mainline_revisions=['A', 'B', 'C'])
577
 
 
578
 
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
579
 
        """When there are parallel roots, check their revnos."""
580
 
        self.assertSortAndIterate(
581
 
            {'A': [],
582
 
             'B': [],
583
 
             'C': ['A', 'B']}.items(),
584
 
            'C',
585
 
            [(0, 'C', 0, (2,), False),
586
 
             (1, 'B', 1, (0,1,1), True),
587
 
             (2, 'A', 0, (1,), True),
588
 
             ],
589
 
            True
590
 
            )
591
 
 
592
 
    def test_revnos_are_globally_assigned(self):
593
 
        """revnos are assigned according to the revision they derive from."""
594
 
        # in this test we setup a number of branches that all derive from
595
 
        # the first revision, and then merge them one at a time, which
596
 
        # should give the revisions as they merge numbers still deriving from
597
 
        # the revision were based on.
598
 
        # merge 3: J: ['G', 'I']
599
 
        # branch 3:
600
 
        #  I: ['H']
601
 
        #  H: ['A']
602
 
        # merge 2: G: ['D', 'F']
603
 
        # branch 2:
604
 
        #  F: ['E']
605
 
        #  E: ['A']
606
 
        # merge 1: D: ['A', 'C']
607
 
        # branch 1:
608
 
        #  C: ['B']
609
 
        #  B: ['A']
610
 
        # root: A: []
611
 
        self.assertSortAndIterate(
612
 
            {'J': ['G', 'I'],
613
 
             'I': ['H',],
614
 
             'H': ['A'],
615
 
             'G': ['D', 'F'],
616
 
             'F': ['E'],
617
 
             'E': ['A'],
618
 
             'D': ['A', 'C'],
619
 
             'C': ['B'],
620
 
             'B': ['A'],
621
 
             'A': [],
622
 
             }.items(),
623
 
            'J',
624
 
            [(0, 'J', 0, (4,), False),
625
 
             (1, 'I', 1, (1,3,2), False),
626
 
             (2, 'H', 1, (1,3,1), True),
627
 
             (3, 'G', 0, (3,), False),
628
 
             (4, 'F', 1, (1,2,2), False),
629
 
             (5, 'E', 1, (1,2,1), True),
630
 
             (6, 'D', 0, (2,), False),
631
 
             (7, 'C', 1, (1,1,2), False),
632
 
             (8, 'B', 1, (1,1,1), True),
633
 
             (9, 'A', 0, (1,), True),
634
 
             ],
635
 
            True
636
 
            )
637
 
 
638
 
    def test_roots_and_sub_branches_versus_ghosts(self):
639
 
        """Extra roots and their mini branches use the same numbering.
640
 
 
641
 
        All of them use the 0-node numbering.
642
 
        """
643
 
        #       A D   K
644
 
        #       | |\  |\
645
 
        #       B E F L M
646
 
        #       | |/  |/
647
 
        #       C G   N
648
 
        #       |/    |\
649
 
        #       H I   O P
650
 
        #       |/    |/
651
 
        #       J     Q
652
 
        #       |.---'
653
 
        #       R
654
 
        self.assertSortAndIterate(
655
 
            {'A': [],
656
 
             'B': ['A'],
657
 
             'C': ['B'],
658
 
             'D': [],
659
 
             'E': ['D'],
660
 
             'F': ['D'],
661
 
             'G': ['E', 'F'],
662
 
             'H': ['C', 'G'],
663
 
             'I': [],
664
 
             'J': ['H', 'I'],
665
 
             'K': [],
666
 
             'L': ['K'],
667
 
             'M': ['K'],
668
 
             'N': ['L', 'M'],
669
 
             'O': ['N'],
670
 
             'P': ['N'],
671
 
             'Q': ['O', 'P'],
672
 
             'R': ['J', 'Q'],
673
 
            }.items(),
674
 
            'R',
675
 
            [( 0, 'R', 0, (6,), False),
676
 
             ( 1, 'Q', 1, (0,4,5), False),
677
 
             ( 2, 'P', 2, (0,6,1), True),
678
 
             ( 3, 'O', 1, (0,4,4), False),
679
 
             ( 4, 'N', 1, (0,4,3), False),
680
 
             ( 5, 'M', 2, (0,5,1), True),
681
 
             ( 6, 'L', 1, (0,4,2), False),
682
 
             ( 7, 'K', 1, (0,4,1), True),
683
 
             ( 8, 'J', 0, (5,), False),
684
 
             ( 9, 'I', 1, (0,3,1), True),
685
 
             (10, 'H', 0, (4,), False),
686
 
             (11, 'G', 1, (0,1,3), False),
687
 
             (12, 'F', 2, (0,2,1), True),
688
 
             (13, 'E', 1, (0,1,2), False),
689
 
             (14, 'D', 1, (0,1,1), True),
690
 
             (15, 'C', 0, (3,), False),
691
 
             (16, 'B', 0, (2,), False),
692
 
             (17, 'A', 0, (1,), True),
693
 
             ],
694
 
            True
695
 
            )
 
279
            mainline_revisions=[None, 'A']
 
280
            )
 
281