« back to all changes in this revision
Viewing changes to bzrlib/tests/test_tsort.py
- browse files at revision 1628
- compare with another revision
- compare with revision 1216
- download diff
- download tarball
- view history from revision 1628
- Committer: Canonical.com Patch Queue Manager
- Date: 2006-03-29 07:59:55 UTC
- mfrom: (1626.2.1 integration)
- Revision ID: pqm@pqm.ubuntu.com-20060329075955-de865fe54faae442
Merge in merge_sort facility.
added
removed
bzrlib/tests/test_tsort.py
19
19
20
20
21
21
from bzrlib.tests import TestCase
22
from bzrlib.tsort import topo_sort, TopoSorter
22
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
23
23
from bzrlib.errors import GraphCycleError
24
24
25
25
84
84
(7, [2, 3]),
85
85
(8, [0, 1, 4, 5, 6])]),
86
86
[0, 1, 2, 3, 4, 5, 6, 7, 8])
87
88
89
class MergeSortTests(TestCase):
90
91
def assertSortAndIterate(self, graph, branch_tip, result_list,
92
mainline_revisions=None):
93
"""Check that merge based sorting and iter_topo_order on graph works."""
94
self.assertEquals(result_list,
95
merge_sort(graph, branch_tip, mainline_revisions=mainline_revisions))
96
self.assertEqual(result_list,
97
list(MergeSorter(
98
graph,
99
branch_tip,
100
mainline_revisions=mainline_revisions).iter_topo_order()))
101
102
def test_merge_sort_empty(self):
103
# sorting of an emptygraph does not error
104
self.assertSortAndIterate({}, None, [])
105
106
def test_merge_sort_not_empty_no_tip(self):
107
# merge sorting of a branch starting with None should result
108
# in an empty list: no revisions are dragged in.
109
self.assertSortAndIterate({0: []}.items(), None, [])
110
111
def test_merge_sort_one_revision(self):
112
# sorting with one revision as the tip returns the correct fields:
113
# sequence - 0, revision id, merge depth - 0, end_of_merge
114
self.assertSortAndIterate({'id': []}.items(),
115
'id',
116
[(0, 'id', 0, True)])
117
118
def test_sequence_numbers_increase_no_merges(self):
119
# emit a few revisions with no merges to check the sequence
120
# numbering works in trivial cases
121
self.assertSortAndIterate(
122
{'A': [],
123
'B': ['A'],
124
'C': ['B']}.items(),
125
'C',
126
[(0, 'C', 0, False),
127
(1, 'B', 0, False),
128
(2, 'A', 0, True),
129
]
130
)
131
132
def test_sequence_numbers_increase_with_merges(self):
133
# test that sequence numbers increase across merges
134
self.assertSortAndIterate(
135
{'A': [],
136
'B': ['A'],
137
'C': ['A', 'B']}.items(),
138
'C',
139
[(0, 'C', 0, False),
140
(1, 'B', 1, True),
141
(2, 'A', 0, True),
142
]
143
)
144
145
def test_merge_depth_with_nested_merges(self):
146
# the merge depth marker should reflect the depth of the revision
147
# in terms of merges out from the mainline
148
# revid, depth, parents:
149
# A 0 [D, B]
150
# B 1 [C, F]
151
# C 1 [H]
152
# D 0 [H, E]
153
# E 1 [G, F]
154
# F 2 [G]
155
# G 1 [H]
156
# H 0
157
self.assertSortAndIterate(
158
{'A': ['D', 'B'],
159
'B': ['C', 'F'],
160
'C': ['H'],
161
'D': ['H', 'E'],
162
'E': ['G', 'F'],
163
'F': ['G'],
164
'G': ['H'],
165
'H': []
166
}.items(),
167
'A',
168
[(0, 'A', 0, False),
169
(1, 'B', 1, False),
170
(2, 'C', 1, True),
171
(3, 'D', 0, False),
172
(4, 'E', 1, False),
173
(5, 'F', 2, True),
174
(6, 'G', 1, True),
175
(7, 'H', 0, True),
176
]
177
)
178
179
def test_end_of_merge_not_last_revision_in_branch(self):
180
# within a branch only the last revision gets an
181
# end of merge marker.
182
self.assertSortAndIterate(
183
{'A': ['B'],
184
'B': [],
185
},
186
'A',
187
[(0, 'A', 0, False),
188
(1, 'B', 0, True)
189
]
190
)
191
192
def test_end_of_merge_multiple_revisions_merged_at_once(self):
193
# when multiple branches are merged at once, both of their
194
# branch-endpoints should be listed as end-of-merge.
195
# Also, the order of the multiple merges should be
196
# left-right shown top to bottom.
197
# * means end of merge
198
# A 0 [H, B, E]
199
# B 1 [D, C]
200
# C 2 [D] *
201
# D 1 [H] *
202
# E 1 [G, F]
203
# F 2 [G] *
204
# G 1 [H] *
205
# H 0 [] *
206
self.assertSortAndIterate(
207
{'A': ['H', 'B', 'E'],
208
'B': ['D', 'C'],
209
'C': ['D'],
210
'D': ['H'],
211
'E': ['G', 'F'],
212
'F': ['G'],
213
'G': ['H'],
214
'H': [],
215
},
216
'A',
217
[(0, 'A', 0, False),
218
(1, 'B', 1, False),
219
(2, 'C', 2, True),
220
(3, 'D', 1, True),
221
(4, 'E', 1, False),
222
(5, 'F', 2, True),
223
(6, 'G', 1, True),
224
(7, 'H', 0, True),
225
]
226
)
227
228
def test_mainline_revs_partial(self):
229
# when a mainline_revisions list is passed this must
230
# override the graphs idea of mainline, and must also
231
# truncate the output to the specified range, if needed.
232
# so we test both at once: a mainline_revisions list that
233
# disagrees with the graph about which revs are 'mainline'
234
# and also truncates the output.
235
# graph:
236
# A 0 [E, B]
237
# B 1 [D, C]
238
# C 2 [D]
239
# D 1 [E]
240
# E 0
241
# with a mainline of NONE,E,A (the inferred one) this will show the merge
242
# depths above.
243
# with a overriden mainline of NONE,E,D,B,A it should show:
244
# A 0
245
# B 0
246
# C 1
247
# D 0
248
# E 0
249
# and thus when truncated to D,B,A it should show
250
# A 0
251
# B 0
252
# C 1
253
# because C is brought in by B in this view and D
254
# is the terminating revision id
255
self.assertSortAndIterate(
256
{'A': ['E', 'B'],
257
'B': ['D', 'C'],
258
'C': ['D'],
259
'D': ['E'],
260
'E': []
261
},
262
'A',
263
[(0, 'A', 0, False),
264
(1, 'B', 0, False),
265
(2, 'C', 1, True),
266
],
267
mainline_revisions=['D', 'B', 'A']
268
)
269
270
def test_mainline_revs_with_none(self):
271
# a simple test to ensure that a mainline_revs
272
# list which goes all the way to None works
273
self.assertSortAndIterate(
274
{'A': [],
275
},
276
'A',
277
[(0, 'A', 0, True),
278
],
279
mainline_revisions=[None, 'A']
280
)
281
Loggerhead is a web-based interface for Breezy
Version: 2.0.1