/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

First attempt to merge .dev and resolve the conflicts (but tests are 
failing)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
1
 
# Copyright (C) 2005 by Canonical Ltd
 
1
# Copyright (C) 2005 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
21
21
from bzrlib.tests import TestCase
22
22
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
23
23
from bzrlib.errors import GraphCycleError
 
24
from bzrlib.revision import NULL_REVISION
24
25
 
25
26
 
26
27
class TopoSortTests(TestCase):
85
86
                                   (8, [0, 1, 4, 5, 6])]),
86
87
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
87
88
 
 
89
    def test_tsort_unincluded_parent(self):
 
90
        """Sort nodes, but don't include some parents in the output"""
 
91
        self.assertSortAndIterate([(0, [1]),
 
92
                                   (1, [2])],
 
93
                                   [1, 0])
 
94
 
88
95
 
89
96
class MergeSortTests(TestCase):
90
97
 
91
98
    def assertSortAndIterate(self, graph, branch_tip, result_list,
92
 
            mainline_revisions=None):
 
99
            generate_revno, mainline_revisions=None):
93
100
        """Check that merge based sorting and iter_topo_order on graph works."""
 
101
        value = merge_sort(graph, branch_tip,
 
102
                           mainline_revisions=mainline_revisions,
 
103
                           generate_revno=generate_revno)
 
104
        if result_list != value:
 
105
            import pprint
 
106
            self.assertEqualDiff(pprint.pformat(result_list),
 
107
                                 pprint.pformat(value))
94
108
        self.assertEquals(result_list,
95
 
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
 
109
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
 
110
                generate_revno=generate_revno))
96
111
        self.assertEqual(result_list,
97
112
            list(MergeSorter(
98
113
                graph,
99
114
                branch_tip,
100
 
                mainline_revisions=mainline_revisions).iter_topo_order()))
 
115
                mainline_revisions=mainline_revisions,
 
116
                generate_revno=generate_revno,
 
117
                ).iter_topo_order()))
101
118
 
102
119
    def test_merge_sort_empty(self):
103
120
        # sorting of an emptygraph does not error
104
 
        self.assertSortAndIterate({}, None, [])
 
121
        self.assertSortAndIterate({}, None, [], False)
 
122
        self.assertSortAndIterate({}, None, [], True)
 
123
        self.assertSortAndIterate({}, NULL_REVISION, [], False)
 
124
        self.assertSortAndIterate({}, NULL_REVISION, [], True)
105
125
 
106
126
    def test_merge_sort_not_empty_no_tip(self):
107
127
        # merge sorting of a branch starting with None should result
108
128
        # in an empty list: no revisions are dragged in.
109
 
        self.assertSortAndIterate({0: []}.items(), None, [])
 
129
        self.assertSortAndIterate({0: []}.items(), None, [], False)
 
130
        self.assertSortAndIterate({0: []}.items(), None, [], True)
110
131
 
111
132
    def test_merge_sort_one_revision(self):
112
133
        # sorting with one revision as the tip returns the correct fields:
113
134
        # sequence - 0, revision id, merge depth - 0, end_of_merge
114
135
        self.assertSortAndIterate({'id': []}.items(),
115
136
                                  'id',
116
 
                                  [(0, 'id', 0, True)])
 
137
                                  [(0, 'id', 0, True)],
 
138
                                  False)
 
139
        self.assertSortAndIterate({'id': []}.items(),
 
140
                                  'id',
 
141
                                  [(0, 'id', 0, (1,), True)],
 
142
                                  True)
117
143
    
118
144
    def test_sequence_numbers_increase_no_merges(self):
119
145
        # emit a few revisions with no merges to check the sequence
126
152
            [(0, 'C', 0, False),
127
153
             (1, 'B', 0, False),
128
154
             (2, 'A', 0, True),
129
 
             ]
 
155
             ],
 
156
            False
 
157
            )
 
158
        self.assertSortAndIterate(
 
159
            {'A': [],
 
160
             'B': ['A'],
 
161
             'C': ['B']}.items(),
 
162
            'C',
 
163
            [(0, 'C', 0, (3,), False),
 
164
             (1, 'B', 0, (2,), False),
 
165
             (2, 'A', 0, (1,), True),
 
166
             ],
 
167
            True
130
168
            )
131
169
 
132
170
    def test_sequence_numbers_increase_with_merges(self):
139
177
            [(0, 'C', 0, False),
140
178
             (1, 'B', 1, True),
141
179
             (2, 'A', 0, True),
142
 
             ]
143
 
            )
144
 
        
 
180
             ],
 
181
            False
 
182
            )
 
183
        self.assertSortAndIterate(
 
184
            {'A': [],
 
185
             'B': ['A'],
 
186
             'C': ['A', 'B']}.items(),
 
187
            'C',
 
188
            [(0, 'C', 0, (2,), False),
 
189
             (1, 'B', 1, (1,1,1), True),
 
190
             (2, 'A', 0, (1,), True),
 
191
             ],
 
192
            True
 
193
            )
 
194
 
 
195
    def test_merge_sort_race(self):
 
196
        # A
 
197
        # |
 
198
        # B-.
 
199
        # |\ \
 
200
        # | | C
 
201
        # | |/
 
202
        # | D
 
203
        # |/
 
204
        # F
 
205
        graph = {'A': [],
 
206
                 'B': ['A'],
 
207
                 'C': ['B'],
 
208
                 'D': ['B', 'C'],
 
209
                 'F': ['B', 'D'],
 
210
                 }
 
211
        self.assertSortAndIterate(graph, 'F',
 
212
            [(0, 'F', 0, (3,), False),
 
213
             (1, 'D', 1, (2,2,1), False),
 
214
             (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
 
215
             (3, 'B', 0, (2,), False),
 
216
             (4, 'A', 0, (1,), True),
 
217
             ], True)
 
218
        # A
 
219
        # |
 
220
        # B-.
 
221
        # |\ \
 
222
        # | X C
 
223
        # | |/
 
224
        # | D
 
225
        # |/
 
226
        # F
 
227
        graph = {'A': [],
 
228
                 'B': ['A'],
 
229
                 'C': ['B'],
 
230
                 'X': ['B'],
 
231
                 'D': ['X', 'C'],
 
232
                 'F': ['B', 'D'],
 
233
                 }
 
234
        self.assertSortAndIterate(graph, 'F',
 
235
            [(0, 'F', 0, (3,), False),
 
236
             (1, 'D', 1, (2,1,2), False),
 
237
             (2, 'C', 2, (2,2,1), True),
 
238
             (3, 'X', 1, (2,1,1), True),
 
239
             (4, 'B', 0, (2,), False),
 
240
             (5, 'A', 0, (1,), True),
 
241
             ], True)
 
242
 
145
243
    def test_merge_depth_with_nested_merges(self):
146
244
        # the merge depth marker should reflect the depth of the revision
147
245
        # in terms of merges out from the mainline
173
271
             (5, 'F', 2, True),
174
272
             (6, 'G', 1, True),
175
273
             (7, 'H', 0, True),
176
 
             ]
177
 
            )
178
 
 
 
274
             ],
 
275
            False
 
276
            )
 
277
        self.assertSortAndIterate(
 
278
            {'A': ['D', 'B'],
 
279
             'B': ['C', 'F'],
 
280
             'C': ['H'],
 
281
             'D': ['H', 'E'],
 
282
             'E': ['G', 'F'],
 
283
             'F': ['G'],
 
284
             'G': ['H'],
 
285
             'H': []
 
286
             }.items(),
 
287
            'A',
 
288
            [(0, 'A', 0, (3,),  False),
 
289
             (1, 'B', 1, (1,3,2), False),
 
290
             (2, 'C', 1, (1,3,1), True),
 
291
             (3, 'D', 0, (2,), False),
 
292
             (4, 'E', 1, (1,1,2), False),
 
293
             (5, 'F', 2, (1,2,1), True),
 
294
             (6, 'G', 1, (1,1,1), True),
 
295
             (7, 'H', 0, (1,), True),
 
296
             ],
 
297
            True
 
298
            )
 
299
 
 
300
    def test_dotted_revnos_with_simple_merges(self):
 
301
        # A         1
 
302
        # |\
 
303
        # B C       2, 1.1.1
 
304
        # | |\
 
305
        # D E F     3, 1.1.2, 1.2.1
 
306
        # |/ /|
 
307
        # G H I     4, 1.2.2, 1.3.1
 
308
        # |/ /
 
309
        # J K       5, 1.3.2
 
310
        # |/
 
311
        # L         6
 
312
        self.assertSortAndIterate(
 
313
            {'A': [],
 
314
             'B': ['A'],
 
315
             'C': ['A'],
 
316
             'D': ['B'],
 
317
             'E': ['C'],
 
318
             'F': ['C'],
 
319
             'G': ['D', 'E'],
 
320
             'H': ['F'],
 
321
             'I': ['F'],
 
322
             'J': ['G', 'H'],
 
323
             'K': ['I'],
 
324
             'L': ['J', 'K'],
 
325
            }.items(),
 
326
            'L',
 
327
            [(0, 'L', 0, (6,), False),
 
328
             (1, 'K', 1, (1,3,2), False),
 
329
             (2, 'I', 1, (1,3,1), True),
 
330
             (3, 'J', 0, (5,), False),
 
331
             (4, 'H', 1, (1,2,2), False),
 
332
             (5, 'F', 1, (1,2,1), True),
 
333
             (6, 'G', 0, (4,), False),
 
334
             (7, 'E', 1, (1,1,2), False),
 
335
             (8, 'C', 1, (1,1,1), True),
 
336
             (9, 'D', 0, (3,), False),
 
337
             (10, 'B', 0, (2,), False),
 
338
             (11, 'A', 0, (1,),  True),
 
339
             ],
 
340
            True
 
341
            )
 
342
        # Adding a shortcut from the first revision should not change any of
 
343
        # the existing numbers
 
344
        self.assertSortAndIterate(
 
345
            {'A': [],
 
346
             'B': ['A'],
 
347
             'C': ['A'],
 
348
             'D': ['B'],
 
349
             'E': ['C'],
 
350
             'F': ['C'],
 
351
             'G': ['D', 'E'],
 
352
             'H': ['F'],
 
353
             'I': ['F'],
 
354
             'J': ['G', 'H'],
 
355
             'K': ['I'],
 
356
             'L': ['J', 'K'],
 
357
             'M': ['A'],
 
358
             'N': ['L', 'M'],
 
359
            }.items(),
 
360
            'N',
 
361
            [(0, 'N', 0, (7,), False),
 
362
             (1, 'M', 1, (1,4,1), True),
 
363
             (2, 'L', 0, (6,), False),
 
364
             (3, 'K', 1, (1,3,2), False),
 
365
             (4, 'I', 1, (1,3,1), True),
 
366
             (5, 'J', 0, (5,), False),
 
367
             (6, 'H', 1, (1,2,2), False),
 
368
             (7, 'F', 1, (1,2,1), True),
 
369
             (8, 'G', 0, (4,), False),
 
370
             (9, 'E', 1, (1,1,2), False),
 
371
             (10, 'C', 1, (1,1,1), True),
 
372
             (11, 'D', 0, (3,), False),
 
373
             (12, 'B', 0, (2,), False),
 
374
             (13, 'A', 0, (1,),  True),
 
375
             ],
 
376
            True
 
377
            )
 
378
 
179
379
    def test_end_of_merge_not_last_revision_in_branch(self):
180
380
        # within a branch only the last revision gets an
181
381
        # end of merge marker.
186
386
            'A',
187
387
            [(0, 'A', 0, False),
188
388
             (1, 'B', 0, True)
189
 
             ]
 
389
             ],
 
390
            False
 
391
            )
 
392
        self.assertSortAndIterate(
 
393
            {'A': ['B'],
 
394
             'B': [],
 
395
             },
 
396
            'A',
 
397
            [(0, 'A', 0, (2,), False),
 
398
             (1, 'B', 0, (1,), True)
 
399
             ],
 
400
            True
190
401
            )
191
402
 
192
403
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
222
433
             (5, 'F', 2, True),
223
434
             (6, 'G', 1, True),
224
435
             (7, 'H', 0, True),
225
 
             ]
 
436
             ],
 
437
            False
 
438
            )
 
439
        self.assertSortAndIterate(
 
440
            {'A': ['H', 'B', 'E'],
 
441
             'B': ['D', 'C'],
 
442
             'C': ['D'],
 
443
             'D': ['H'],
 
444
             'E': ['G', 'F'],
 
445
             'F': ['G'],
 
446
             'G': ['H'],
 
447
             'H': [],
 
448
             },
 
449
            'A',
 
450
            [(0, 'A', 0, (2,), False),
 
451
             (1, 'B', 1, (1,3,2), False),
 
452
             (2, 'C', 2, (1,4,1), True),
 
453
             (3, 'D', 1, (1,3,1), True),
 
454
             (4, 'E', 1, (1,1,2), False),
 
455
             (5, 'F', 2, (1,2,1), True),
 
456
             (6, 'G', 1, (1,1,1), True),
 
457
             (7, 'H', 0, (1,), True),
 
458
             ],
 
459
            True
226
460
            )
227
461
 
228
462
    def test_mainline_revs_partial(self):
252
486
        # C 1 
253
487
        # because C is brought in by B in this view and D
254
488
        # is the terminating revision id
 
489
        # this should also preserve revision numbers: C should still be 2.1.1
255
490
        self.assertSortAndIterate(
256
491
            {'A': ['E', 'B'],
257
492
             'B': ['D', 'C'],
264
499
             (1, 'B', 0, False),
265
500
             (2, 'C', 1, True),
266
501
             ],
 
502
            False,
 
503
            mainline_revisions=['D', 'B', 'A']
 
504
            )
 
505
        self.assertSortAndIterate(
 
506
            {'A': ['E', 'B'],
 
507
             'B': ['D', 'C'],
 
508
             'C': ['D'],
 
509
             'D': ['E'],
 
510
             'E': []
 
511
             },
 
512
            'A',
 
513
            [(0, 'A', 0, (4,), False),
 
514
             (1, 'B', 0, (3,), False),
 
515
             (2, 'C', 1, (2,1,1), True),
 
516
             ],
 
517
            True,
267
518
            mainline_revisions=['D', 'B', 'A']
268
519
            )
269
520
 
276
527
            'A',
277
528
            [(0, 'A', 0, True),
278
529
             ],
279
 
            mainline_revisions=[None, 'A']
280
 
            )
281
 
 
 
530
            False,
 
531
            mainline_revisions=[None, 'A']
 
532
            )
 
533
        self.assertSortAndIterate(
 
534
            {'A': [],
 
535
             },
 
536
            'A',
 
537
            [(0, 'A', 0, (1,), True),
 
538
             ],
 
539
            True,
 
540
            mainline_revisions=[None, 'A']
 
541
            )
 
542
 
 
543
    def test_mainline_revs_with_ghost(self):
 
544
        # We have a mainline, but the end of it is actually a ghost
 
545
        # The graph that is passed to tsort has had ghosts filtered out, but
 
546
        # the mainline history has not.
 
547
        self.assertSortAndIterate(
 
548
            {'B':[],
 
549
             'C':['B']}.items(),
 
550
            'C',
 
551
            [(0, 'C', 0, (2,), False),
 
552
             (1, 'B', 0, (1,), True),
 
553
             ],
 
554
             True, mainline_revisions=['A', 'B', 'C'])
 
555
 
 
556
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
 
557
        """When there are parallel roots, check their revnos."""
 
558
        self.assertSortAndIterate(
 
559
            {'A': [],
 
560
             'B': [],
 
561
             'C': ['A', 'B']}.items(),
 
562
            'C',
 
563
            [(0, 'C', 0, (2,), False),
 
564
             (1, 'B', 1, (0,1,1), True),
 
565
             (2, 'A', 0, (1,), True),
 
566
             ],
 
567
            True
 
568
            )
 
569
        
 
570
    def test_revnos_are_globally_assigned(self):
 
571
        """revnos are assigned according to the revision they derive from."""
 
572
        # in this test we setup a number of branches that all derive from 
 
573
        # the first revision, and then merge them one at a time, which 
 
574
        # should give the revisions as they merge numbers still deriving from
 
575
        # the revision were based on.
 
576
        # merge 3: J: ['G', 'I']
 
577
        # branch 3:
 
578
        #  I: ['H']
 
579
        #  H: ['A']
 
580
        # merge 2: G: ['D', 'F']
 
581
        # branch 2:
 
582
        #  F: ['E']
 
583
        #  E: ['A']
 
584
        # merge 1: D: ['A', 'C']
 
585
        # branch 1:
 
586
        #  C: ['B']
 
587
        #  B: ['A']
 
588
        # root: A: []
 
589
        self.assertSortAndIterate(
 
590
            {'J': ['G', 'I'],
 
591
             'I': ['H',],
 
592
             'H': ['A'],
 
593
             'G': ['D', 'F'],
 
594
             'F': ['E'],
 
595
             'E': ['A'],
 
596
             'D': ['A', 'C'],
 
597
             'C': ['B'],
 
598
             'B': ['A'],
 
599
             'A': [],
 
600
             }.items(),
 
601
            'J',
 
602
            [(0, 'J', 0, (4,), False),
 
603
             (1, 'I', 1, (1,3,2), False),
 
604
             (2, 'H', 1, (1,3,1), True),
 
605
             (3, 'G', 0, (3,), False),
 
606
             (4, 'F', 1, (1,2,2), False),
 
607
             (5, 'E', 1, (1,2,1), True),
 
608
             (6, 'D', 0, (2,), False),
 
609
             (7, 'C', 1, (1,1,2), False),
 
610
             (8, 'B', 1, (1,1,1), True),
 
611
             (9, 'A', 0, (1,), True),
 
612
             ],
 
613
            True
 
614
            )
 
615
 
 
616
    def test_roots_and_sub_branches_versus_ghosts(self):
 
617
        """Extra roots and their mini branches use the same numbering.
 
618
 
 
619
        All of them use the 0-node numbering.
 
620
        """
 
621
        #       A D   K
 
622
        #       | |\  |\
 
623
        #       B E F L M
 
624
        #       | |/  |/
 
625
        #       C G   N
 
626
        #       |/    |\
 
627
        #       H I   O P
 
628
        #       |/    |/
 
629
        #       J     Q
 
630
        #       |.---'
 
631
        #       R
 
632
        self.assertSortAndIterate(
 
633
            {'A': [],
 
634
             'B': ['A'],
 
635
             'C': ['B'],
 
636
             'D': [],
 
637
             'E': ['D'],
 
638
             'F': ['D'],
 
639
             'G': ['E', 'F'],
 
640
             'H': ['C', 'G'],
 
641
             'I': [],
 
642
             'J': ['H', 'I'],
 
643
             'K': [],
 
644
             'L': ['K'],
 
645
             'M': ['K'],
 
646
             'N': ['L', 'M'],
 
647
             'O': ['N'],
 
648
             'P': ['N'],
 
649
             'Q': ['O', 'P'],
 
650
             'R': ['J', 'Q'],
 
651
            }.items(),
 
652
            'R',
 
653
            [( 0, 'R', 0, (6,), False),
 
654
             ( 1, 'Q', 1, (0,4,5), False),
 
655
             ( 2, 'P', 2, (0,6,1), True),
 
656
             ( 3, 'O', 1, (0,4,4), False),
 
657
             ( 4, 'N', 1, (0,4,3), False),
 
658
             ( 5, 'M', 2, (0,5,1), True),
 
659
             ( 6, 'L', 1, (0,4,2), False),
 
660
             ( 7, 'K', 1, (0,4,1), True),
 
661
             ( 8, 'J', 0, (5,), False),
 
662
             ( 9, 'I', 1, (0,3,1), True),
 
663
             (10, 'H', 0, (4,), False),
 
664
             (11, 'G', 1, (0,1,3), False),
 
665
             (12, 'F', 2, (0,2,1), True),
 
666
             (13, 'E', 1, (0,1,2), False),
 
667
             (14, 'D', 1, (0,1,1), True),
 
668
             (15, 'C', 0, (3,), False),
 
669
             (16, 'B', 0, (2,), False),
 
670
             (17, 'A', 0, (1,), True),
 
671
             ],
 
672
            True
 
673
            )