« back to all changes in this revision
Viewing changes to bzrlib/tests/test_tsort.py
- browse files at revision 2084
- compare with another revision
- compare with revision 1904.2.1
- download diff
- download tarball
- view history from revision 2084
- Committer: Canonical.com Patch Queue Manager
- Date: 2006-10-16 10:03:21 UTC
- mfrom: (1988.4.6 dotted-revno-input.)
- Revision ID: pqm@pqm.ubuntu.com-20061016100321-c4951c9fc020dbd0
(Robert Collins) Output dotted decimal revision numbers during log, and accept them as revision specifiers.
added
removed
bzrlib/tests/test_tsort.py
89
89
class MergeSortTests(TestCase):
90
90
91
91
def assertSortAndIterate(self, graph, branch_tip, result_list,
92
mainline_revisions=None):
92
generate_revno, mainline_revisions=None):
93
93
"""Check that merge based sorting and iter_topo_order on graph works."""
94
94
self.assertEquals(result_list,
95
merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
95
merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions,
96
generate_revno=generate_revno))
96
97
self.assertEqual(result_list,
97
98
list(MergeSorter(
98
99
graph,
99
100
branch_tip,
100
mainline_revisions=mainline_revisions).iter_topo_order()))
101
mainline_revisions=mainline_revisions,
102
generate_revno=generate_revno,
103
).iter_topo_order()))
101
104
102
105
def test_merge_sort_empty(self):
103
106
# sorting of an emptygraph does not error
104
self.assertSortAndIterate({}, None, [])
107
self.assertSortAndIterate({}, None, [], False)
108
self.assertSortAndIterate({}, None, [], True)
105
109
106
110
def test_merge_sort_not_empty_no_tip(self):
107
111
# merge sorting of a branch starting with None should result
108
112
# in an empty list: no revisions are dragged in.
109
self.assertSortAndIterate({0: []}.items(), None, [])
113
self.assertSortAndIterate({0: []}.items(), None, [], False)
114
self.assertSortAndIterate({0: []}.items(), None, [], True)
110
115
111
116
def test_merge_sort_one_revision(self):
112
117
# sorting with one revision as the tip returns the correct fields:
113
118
# sequence - 0, revision id, merge depth - 0, end_of_merge
114
119
self.assertSortAndIterate({'id': []}.items(),
115
120
'id',
116
[(0, 'id', 0, True)])
121
[(0, 'id', 0, True)],
122
False)
123
self.assertSortAndIterate({'id': []}.items(),
124
'id',
125
[(0, 'id', 0, (1,), True)],
126
True)
117
127
118
128
def test_sequence_numbers_increase_no_merges(self):
119
129
# emit a few revisions with no merges to check the sequence
126
136
[(0, 'C', 0, False),
127
137
(1, 'B', 0, False),
128
138
(2, 'A', 0, True),
129
]
139
],
140
False
141
)
142
self.assertSortAndIterate(
143
{'A': [],
144
'B': ['A'],
145
'C': ['B']}.items(),
146
'C',
147
[(0, 'C', 0, (3,), False),
148
(1, 'B', 0, (2,), False),
149
(2, 'A', 0, (1,), True),
150
],
151
True
130
152
)
131
153
132
154
def test_sequence_numbers_increase_with_merges(self):
139
161
[(0, 'C', 0, False),
140
162
(1, 'B', 1, True),
141
163
(2, 'A', 0, True),
142
]
164
],
165
False
166
)
167
self.assertSortAndIterate(
168
{'A': [],
169
'B': ['A'],
170
'C': ['A', 'B']}.items(),
171
'C',
172
[(0, 'C', 0, (2,), False),
173
(1, 'B', 1, (1,1,1), True),
174
(2, 'A', 0, (1,), True),
175
],
176
True
143
177
)
144
178
145
179
def test_merge_depth_with_nested_merges(self):
173
207
(5, 'F', 2, True),
174
208
(6, 'G', 1, True),
175
209
(7, 'H', 0, True),
176
]
210
],
211
False
212
)
213
self.assertSortAndIterate(
214
{'A': ['D', 'B'],
215
'B': ['C', 'F'],
216
'C': ['H'],
217
'D': ['H', 'E'],
218
'E': ['G', 'F'],
219
'F': ['G'],
220
'G': ['H'],
221
'H': []
222
}.items(),
223
'A',
224
[(0, 'A', 0, (3,), False),
225
(1, 'B', 1, (1,2,2), False),
226
(2, 'C', 1, (1,2,1), True),
227
(3, 'D', 0, (2,), False),
228
(4, 'E', 1, (1,1,2), False),
229
(5, 'F', 2, (1,1,1,1,1), True),
230
(6, 'G', 1, (1,1,1), True),
231
(7, 'H', 0, (1,), True),
232
],
233
True
177
234
)
178
235
179
236
def test_end_of_merge_not_last_revision_in_branch(self):
186
243
'A',
187
244
[(0, 'A', 0, False),
188
245
(1, 'B', 0, True)
189
]
246
],
247
False
248
)
249
self.assertSortAndIterate(
250
{'A': ['B'],
251
'B': [],
252
},
253
'A',
254
[(0, 'A', 0, (2,), False),
255
(1, 'B', 0, (1,), True)
256
],
257
True
190
258
)
191
259
192
260
def test_end_of_merge_multiple_revisions_merged_at_once(self):
222
290
(5, 'F', 2, True),
223
291
(6, 'G', 1, True),
224
292
(7, 'H', 0, True),
225
]
293
],
294
False
295
)
296
self.assertSortAndIterate(
297
{'A': ['H', 'B', 'E'],
298
'B': ['D', 'C'],
299
'C': ['D'],
300
'D': ['H'],
301
'E': ['G', 'F'],
302
'F': ['G'],
303
'G': ['H'],
304
'H': [],
305
},
306
'A',
307
[(0, 'A', 0, (2,), False),
308
(1, 'B', 1, (1,2,2), False),
309
(2, 'C', 2, (1,2,1,1,1), True),
310
(3, 'D', 1, (1,2,1), True),
311
(4, 'E', 1, (1,1,2), False),
312
(5, 'F', 2, (1,1,1,1,1), True),
313
(6, 'G', 1, (1,1,1), True),
314
(7, 'H', 0, (1,), True),
315
],
316
True
226
317
)
227
318
228
319
def test_mainline_revs_partial(self):
252
343
# C 1
253
344
# because C is brought in by B in this view and D
254
345
# is the terminating revision id
346
# this should also preserve revision numbers: C should still be 2.1.1
255
347
self.assertSortAndIterate(
256
348
{'A': ['E', 'B'],
257
349
'B': ['D', 'C'],
264
356
(1, 'B', 0, False),
265
357
(2, 'C', 1, True),
266
358
],
359
False,
360
mainline_revisions=['D', 'B', 'A']
361
)
362
self.assertSortAndIterate(
363
{'A': ['E', 'B'],
364
'B': ['D', 'C'],
365
'C': ['D'],
366
'D': ['E'],
367
'E': []
368
},
369
'A',
370
[(0, 'A', 0, (4,), False),
371
(1, 'B', 0, (3,), False),
372
(2, 'C', 1, (2,1,1), True),
373
],
374
True,
267
375
mainline_revisions=['D', 'B', 'A']
268
376
)
269
377
276
384
'A',
277
385
[(0, 'A', 0, True),
278
386
],
387
False,
388
mainline_revisions=[None, 'A']
389
)
390
self.assertSortAndIterate(
391
{'A': [],
392
},
393
'A',
394
[(0, 'A', 0, (1,), True),
395
],
396
True,
279
397
mainline_revisions=[None, 'A']
280
398
)
281
399
400
def test_parallel_root_sequence_numbers_increase_with_merges(self):
401
"""When there are parallel roots, check their revnos."""
402
self.assertSortAndIterate(
403
{'A': [],
404
'B': [],
405
'C': ['A', 'B']}.items(),
406
'C',
407
[(0, 'C', 0, (2,), False),
408
(1, 'B', 1, (0,1,1), True),
409
(2, 'A', 0, (1,), True),
410
],
411
True
412
)
413
414
def test_revnos_are_globally_assigned(self):
415
"""revnos are assigned according to the revision they derive from."""
416
# in this test we setup a number of branches that all derive from
417
# the first revision, and then merge them one at a time, which
418
# should give the revisions as they merge numbers still deriving from
419
# the revision were based on.
420
# merge 3: J: ['G', 'I']
421
# branch 3:
422
# I: ['H']
423
# H: ['A']
424
# merge 2: G: ['D', 'F']
425
# branch 2:
426
# F: ['E']
427
# E: ['A']
428
# merge 1: D: ['A', 'C']
429
# branch 1:
430
# C: ['B']
431
# B: ['A']
432
# root: A: []
433
self.assertSortAndIterate(
434
{'J': ['G', 'I'],
435
'I': ['H',],
436
'H': ['A'],
437
'G': ['D', 'F'],
438
'F': ['E'],
439
'E': ['A'],
440
'D': ['A', 'C'],
441
'C': ['B'],
442
'B': ['A'],
443
'A': [],
444
}.items(),
445
'J',
446
[(0, 'J', 0, (4,), False),
447
(1, 'I', 1, (1,3,2), False),
448
(2, 'H', 1, (1,3,1), True),
449
(3, 'G', 0, (3,), False),
450
(4, 'F', 1, (1,2,2), False),
451
(5, 'E', 1, (1,2,1), True),
452
(6, 'D', 0, (2,), False),
453
(7, 'C', 1, (1,1,2), False),
454
(8, 'B', 1, (1,1,1), True),
455
(9, 'A', 0, (1,), True),
456
],
457
True
458
)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1