← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

Merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
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):
112
113
        # sorting of an emptygraph does not error
113
114
        self.assertSortAndIterate({}, None, [], False)
114
115
        self.assertSortAndIterate({}, None, [], True)
 
116
        self.assertSortAndIterate({}, NULL_REVISION, [], False)
 
117
        self.assertSortAndIterate({}, NULL_REVISION, [], True)
115
118
 
116
119
    def test_merge_sort_not_empty_no_tip(self):
117
120
        # merge sorting of a branch starting with None should result
181
184
             ],
182
185
            True
183
186
            )
184
 
        
 
187
 
 
188
    def test_merge_sort_race(self):
 
189
        # A
 
190
        # |
 
191
        # B-.
 
192
        # |\ \
 
193
        # | | C
 
194
        # | |/
 
195
        # | D
 
196
        # |/
 
197
        # F
 
198
        graph = {'A': [],
 
199
                 'B': ['A'],
 
200
                 'C': ['B'],
 
201
                 'D': ['B', 'C'],
 
202
                 'F': ['B', 'D'],
 
203
                 }
 
204
        self.assertSortAndIterate(graph, 'F',
 
205
            [(0, 'F', 0, (3,), False),
 
206
             (1, 'D', 1, (2,2,1), False),
 
207
             (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
 
208
             (3, 'B', 0, (2,), False),
 
209
             (4, 'A', 0, (1,), True),
 
210
             ], True)
 
211
        # A
 
212
        # |
 
213
        # B-.
 
214
        # |\ \
 
215
        # | X C
 
216
        # | |/
 
217
        # | D
 
218
        # |/
 
219
        # F
 
220
        graph = {'A': [],
 
221
                 'B': ['A'],
 
222
                 'C': ['B'],
 
223
                 'X': ['B'],
 
224
                 'D': ['X', 'C'],
 
225
                 'F': ['B', 'D'],
 
226
                 }
 
227
        self.assertSortAndIterate(graph, 'F',
 
228
            [(0, 'F', 0, (3,), False),
 
229
             (1, 'D', 1, (2,1,2), False),
 
230
             (2, 'C', 2, (2,2,1), True),
 
231
             (3, 'X', 1, (2,1,1), True),
 
232
             (4, 'B', 0, (2,), False),
 
233
             (5, 'A', 0, (1,), True),
 
234
             ], True)
 
235
 
185
236
    def test_merge_depth_with_nested_merges(self):
186
237
        # the merge depth marker should reflect the depth of the revision
187
238
        # in terms of merges out from the mainline
228
279
             }.items(),
229
280
            'A',
230
281
            [(0, 'A', 0, (3,),  False),
231
 
             (1, 'B', 1, (1,2,2), False),
232
 
             (2, 'C', 1, (1,2,1), True),
 
282
             (1, 'B', 1, (1,3,2), False),
 
283
             (2, 'C', 1, (1,3,1), True),
233
284
             (3, 'D', 0, (2,), False),
234
285
             (4, 'E', 1, (1,1,2), False),
235
 
             (5, 'F', 2, (1,1,1,1,1), True),
 
286
             (5, 'F', 2, (1,2,1), True),
236
287
             (6, 'G', 1, (1,1,1), True),
237
288
             (7, 'H', 0, (1,), True),
238
289
             ],
239
290
            True
240
291
            )
241
 
 
 
292
 
 
293
    def test_dotted_revnos_with_simple_merges(self):
 
294
        # A         1
 
295
        # |\
 
296
        # B C       2, 1.1.1
 
297
        # | |\
 
298
        # D E F     3, 1.1.2, 1.2.1
 
299
        # |/ /|
 
300
        # G H I     4, 1.2.2, 1.3.1
 
301
        # |/ /
 
302
        # J K       5, 1.3.2
 
303
        # |/
 
304
        # L         6
 
305
        self.assertSortAndIterate(
 
306
            {'A': [],
 
307
             'B': ['A'],
 
308
             'C': ['A'],
 
309
             'D': ['B'],
 
310
             'E': ['C'],
 
311
             'F': ['C'],
 
312
             'G': ['D', 'E'],
 
313
             'H': ['F'],
 
314
             'I': ['F'],
 
315
             'J': ['G', 'H'],
 
316
             'K': ['I'],
 
317
             'L': ['J', 'K'],
 
318
            }.items(),
 
319
            'L',
 
320
            [(0, 'L', 0, (6,), False),
 
321
             (1, 'K', 1, (1,3,2), False),
 
322
             (2, 'I', 1, (1,3,1), True),
 
323
             (3, 'J', 0, (5,), False),
 
324
             (4, 'H', 1, (1,2,2), False),
 
325
             (5, 'F', 1, (1,2,1), True),
 
326
             (6, 'G', 0, (4,), False),
 
327
             (7, 'E', 1, (1,1,2), False),
 
328
             (8, 'C', 1, (1,1,1), True),
 
329
             (9, 'D', 0, (3,), False),
 
330
             (10, 'B', 0, (2,), False),
 
331
             (11, 'A', 0, (1,),  True),
 
332
             ],
 
333
            True
 
334
            )
 
335
        # Adding a shortcut from the first revision should not change any of
 
336
        # the existing numbers
 
337
        self.assertSortAndIterate(
 
338
            {'A': [],
 
339
             'B': ['A'],
 
340
             'C': ['A'],
 
341
             'D': ['B'],
 
342
             'E': ['C'],
 
343
             'F': ['C'],
 
344
             'G': ['D', 'E'],
 
345
             'H': ['F'],
 
346
             'I': ['F'],
 
347
             'J': ['G', 'H'],
 
348
             'K': ['I'],
 
349
             'L': ['J', 'K'],
 
350
             'M': ['A'],
 
351
             'N': ['L', 'M'],
 
352
            }.items(),
 
353
            'N',
 
354
            [(0, 'N', 0, (7,), False),
 
355
             (1, 'M', 1, (1,4,1), True),
 
356
             (2, 'L', 0, (6,), False),
 
357
             (3, 'K', 1, (1,3,2), False),
 
358
             (4, 'I', 1, (1,3,1), True),
 
359
             (5, 'J', 0, (5,), False),
 
360
             (6, 'H', 1, (1,2,2), False),
 
361
             (7, 'F', 1, (1,2,1), True),
 
362
             (8, 'G', 0, (4,), False),
 
363
             (9, 'E', 1, (1,1,2), False),
 
364
             (10, 'C', 1, (1,1,1), True),
 
365
             (11, 'D', 0, (3,), False),
 
366
             (12, 'B', 0, (2,), False),
 
367
             (13, 'A', 0, (1,),  True),
 
368
             ],
 
369
            True
 
370
            )
 
371
 
242
372
    def test_end_of_merge_not_last_revision_in_branch(self):
243
373
        # within a branch only the last revision gets an
244
374
        # end of merge marker.
311
441
             },
312
442
            'A',
313
443
            [(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),
 
444
             (1, 'B', 1, (1,3,2), False),
 
445
             (2, 'C', 2, (1,4,1), True),
 
446
             (3, 'D', 1, (1,3,1), True),
317
447
             (4, 'E', 1, (1,1,2), False),
318
 
             (5, 'F', 2, (1,1,1,1,1), True),
 
448
             (5, 'F', 2, (1,2,1), True),
319
449
             (6, 'G', 1, (1,1,1), True),
320
450
             (7, 'H', 0, (1,), True),
321
451
             ],