← 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: Robert Collins
  • Date: 2007-07-04 08:08:13 UTC
  • mfrom: (2572 +trunk)
  • mto: This revision was merged to the branch mainline in revision 2587.
  • Revision ID: robertc@robertcollins.net-20070704080813-wzebx0r88fvwj5rq
Merge bzr.dev.

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
85
85
                                   (8, [0, 1, 4, 5, 6])]),
86
86
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
87
87
 
 
88
    def test_tsort_unincluded_parent(self):
 
89
        """Sort nodes, but don't include some parents in the output"""
 
90
        self.assertSortAndIterate([(0, [1]),
 
91
                                   (1, [2])],
 
92
                                   [1, 0])
 
93
 
88
94
 
89
95
class MergeSortTests(TestCase):
90
96
 
91
97
    def assertSortAndIterate(self, graph, branch_tip, result_list,
92
 
            mainline_revisions=None):
 
98
            generate_revno, mainline_revisions=None):
93
99
        """Check that merge based sorting and iter_topo_order on graph works."""
94
100
        self.assertEquals(result_list,
95
 
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
 
101
            merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
 
102
                generate_revno=generate_revno))
96
103
        self.assertEqual(result_list,
97
104
            list(MergeSorter(
98
105
                graph,
99
106
                branch_tip,
100
 
                mainline_revisions=mainline_revisions).iter_topo_order()))
 
107
                mainline_revisions=mainline_revisions,
 
108
                generate_revno=generate_revno,
 
109
                ).iter_topo_order()))
101
110
 
102
111
    def test_merge_sort_empty(self):
103
112
        # sorting of an emptygraph does not error
104
 
        self.assertSortAndIterate({}, None, [])
 
113
        self.assertSortAndIterate({}, None, [], False)
 
114
        self.assertSortAndIterate({}, None, [], True)
105
115
 
106
116
    def test_merge_sort_not_empty_no_tip(self):
107
117
        # merge sorting of a branch starting with None should result
108
118
        # in an empty list: no revisions are dragged in.
109
 
        self.assertSortAndIterate({0: []}.items(), None, [])
 
119
        self.assertSortAndIterate({0: []}.items(), None, [], False)
 
120
        self.assertSortAndIterate({0: []}.items(), None, [], True)
110
121
 
111
122
    def test_merge_sort_one_revision(self):
112
123
        # sorting with one revision as the tip returns the correct fields:
113
124
        # sequence - 0, revision id, merge depth - 0, end_of_merge
114
125
        self.assertSortAndIterate({'id': []}.items(),
115
126
                                  'id',
116
 
                                  [(0, 'id', 0, True)])
 
127
                                  [(0, 'id', 0, True)],
 
128
                                  False)
 
129
        self.assertSortAndIterate({'id': []}.items(),
 
130
                                  'id',
 
131
                                  [(0, 'id', 0, (1,), True)],
 
132
                                  True)
117
133
    
118
134
    def test_sequence_numbers_increase_no_merges(self):
119
135
        # emit a few revisions with no merges to check the sequence
126
142
            [(0, 'C', 0, False),
127
143
             (1, 'B', 0, False),
128
144
             (2, 'A', 0, True),
129
 
             ]
 
145
             ],
 
146
            False
 
147
            )
 
148
        self.assertSortAndIterate(
 
149
            {'A': [],
 
150
             'B': ['A'],
 
151
             'C': ['B']}.items(),
 
152
            'C',
 
153
            [(0, 'C', 0, (3,), False),
 
154
             (1, 'B', 0, (2,), False),
 
155
             (2, 'A', 0, (1,), True),
 
156
             ],
 
157
            True
130
158
            )
131
159
 
132
160
    def test_sequence_numbers_increase_with_merges(self):
139
167
            [(0, 'C', 0, False),
140
168
             (1, 'B', 1, True),
141
169
             (2, 'A', 0, True),
142
 
             ]
 
170
             ],
 
171
            False
 
172
            )
 
173
        self.assertSortAndIterate(
 
174
            {'A': [],
 
175
             'B': ['A'],
 
176
             'C': ['A', 'B']}.items(),
 
177
            'C',
 
178
            [(0, 'C', 0, (2,), False),
 
179
             (1, 'B', 1, (1,1,1), True),
 
180
             (2, 'A', 0, (1,), True),
 
181
             ],
 
182
            True
143
183
            )
144
184
        
145
185
    def test_merge_depth_with_nested_merges(self):
173
213
             (5, 'F', 2, True),
174
214
             (6, 'G', 1, True),
175
215
             (7, 'H', 0, True),
176
 
             ]
 
216
             ],
 
217
            False
 
218
            )
 
219
        self.assertSortAndIterate(
 
220
            {'A': ['D', 'B'],
 
221
             'B': ['C', 'F'],
 
222
             'C': ['H'],
 
223
             'D': ['H', 'E'],
 
224
             'E': ['G', 'F'],
 
225
             'F': ['G'],
 
226
             'G': ['H'],
 
227
             'H': []
 
228
             }.items(),
 
229
            'A',
 
230
            [(0, 'A', 0, (3,),  False),
 
231
             (1, 'B', 1, (1,2,2), False),
 
232
             (2, 'C', 1, (1,2,1), True),
 
233
             (3, 'D', 0, (2,), False),
 
234
             (4, 'E', 1, (1,1,2), False),
 
235
             (5, 'F', 2, (1,1,1,1,1), True),
 
236
             (6, 'G', 1, (1,1,1), True),
 
237
             (7, 'H', 0, (1,), True),
 
238
             ],
 
239
            True
177
240
            )
178
241
 
179
242
    def test_end_of_merge_not_last_revision_in_branch(self):
186
249
            'A',
187
250
            [(0, 'A', 0, False),
188
251
             (1, 'B', 0, True)
189
 
             ]
 
252
             ],
 
253
            False
 
254
            )
 
255
        self.assertSortAndIterate(
 
256
            {'A': ['B'],
 
257
             'B': [],
 
258
             },
 
259
            'A',
 
260
            [(0, 'A', 0, (2,), False),
 
261
             (1, 'B', 0, (1,), True)
 
262
             ],
 
263
            True
190
264
            )
191
265
 
192
266
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
222
296
             (5, 'F', 2, True),
223
297
             (6, 'G', 1, True),
224
298
             (7, 'H', 0, True),
225
 
             ]
 
299
             ],
 
300
            False
 
301
            )
 
302
        self.assertSortAndIterate(
 
303
            {'A': ['H', 'B', 'E'],
 
304
             'B': ['D', 'C'],
 
305
             'C': ['D'],
 
306
             'D': ['H'],
 
307
             'E': ['G', 'F'],
 
308
             'F': ['G'],
 
309
             'G': ['H'],
 
310
             'H': [],
 
311
             },
 
312
            'A',
 
313
            [(0, 'A', 0, (2,), False),
 
314
             (1, 'B', 1, (1,2,2), False),
 
315
             (2, 'C', 2, (1,2,1,1,1), True),
 
316
             (3, 'D', 1, (1,2,1), True),
 
317
             (4, 'E', 1, (1,1,2), False),
 
318
             (5, 'F', 2, (1,1,1,1,1), True),
 
319
             (6, 'G', 1, (1,1,1), True),
 
320
             (7, 'H', 0, (1,), True),
 
321
             ],
 
322
            True
226
323
            )
227
324
 
228
325
    def test_mainline_revs_partial(self):
252
349
        # C 1 
253
350
        # because C is brought in by B in this view and D
254
351
        # is the terminating revision id
 
352
        # this should also preserve revision numbers: C should still be 2.1.1
255
353
        self.assertSortAndIterate(
256
354
            {'A': ['E', 'B'],
257
355
             'B': ['D', 'C'],
264
362
             (1, 'B', 0, False),
265
363
             (2, 'C', 1, True),
266
364
             ],
 
365
            False,
 
366
            mainline_revisions=['D', 'B', 'A']
 
367
            )
 
368
        self.assertSortAndIterate(
 
369
            {'A': ['E', 'B'],
 
370
             'B': ['D', 'C'],
 
371
             'C': ['D'],
 
372
             'D': ['E'],
 
373
             'E': []
 
374
             },
 
375
            'A',
 
376
            [(0, 'A', 0, (4,), False),
 
377
             (1, 'B', 0, (3,), False),
 
378
             (2, 'C', 1, (2,1,1), True),
 
379
             ],
 
380
            True,
267
381
            mainline_revisions=['D', 'B', 'A']
268
382
            )
269
383
 
276
390
            'A',
277
391
            [(0, 'A', 0, True),
278
392
             ],
 
393
            False,
 
394
            mainline_revisions=[None, 'A']
 
395
            )
 
396
        self.assertSortAndIterate(
 
397
            {'A': [],
 
398
             },
 
399
            'A',
 
400
            [(0, 'A', 0, (1,), True),
 
401
             ],
 
402
            True,
279
403
            mainline_revisions=[None, 'A']
280
404
            )
281
405
 
 
406
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
 
407
        """When there are parallel roots, check their revnos."""
 
408
        self.assertSortAndIterate(
 
409
            {'A': [],
 
410
             'B': [],
 
411
             'C': ['A', 'B']}.items(),
 
412
            'C',
 
413
            [(0, 'C', 0, (2,), False),
 
414
             (1, 'B', 1, (0,1,1), True),
 
415
             (2, 'A', 0, (1,), True),
 
416
             ],
 
417
            True
 
418
            )
 
419
        
 
420
    def test_revnos_are_globally_assigned(self):
 
421
        """revnos are assigned according to the revision they derive from."""
 
422
        # in this test we setup a number of branches that all derive from 
 
423
        # the first revision, and then merge them one at a time, which 
 
424
        # should give the revisions as they merge numbers still deriving from
 
425
        # the revision were based on.
 
426
        # merge 3: J: ['G', 'I']
 
427
        # branch 3:
 
428
        #  I: ['H']
 
429
        #  H: ['A']
 
430
        # merge 2: G: ['D', 'F']
 
431
        # branch 2:
 
432
        #  F: ['E']
 
433
        #  E: ['A']
 
434
        # merge 1: D: ['A', 'C']
 
435
        # branch 1:
 
436
        #  C: ['B']
 
437
        #  B: ['A']
 
438
        # root: A: []
 
439
        self.assertSortAndIterate(
 
440
            {'J': ['G', 'I'],
 
441
             'I': ['H',],
 
442
             'H': ['A'],
 
443
             'G': ['D', 'F'],
 
444
             'F': ['E'],
 
445
             'E': ['A'],
 
446
             'D': ['A', 'C'],
 
447
             'C': ['B'],
 
448
             'B': ['A'],
 
449
             'A': [],
 
450
             }.items(),
 
451
            'J',
 
452
            [(0, 'J', 0, (4,), False),
 
453
             (1, 'I', 1, (1,3,2), False),
 
454
             (2, 'H', 1, (1,3,1), True),
 
455
             (3, 'G', 0, (3,), False),
 
456
             (4, 'F', 1, (1,2,2), False),
 
457
             (5, 'E', 1, (1,2,1), True),
 
458
             (6, 'D', 0, (2,), False),
 
459
             (7, 'C', 1, (1,1,2), False),
 
460
             (8, 'B', 1, (1,1,1), True),
 
461
             (9, 'A', 0, (1,), True),
 
462
             ],
 
463
            True
 
464
            )