1
# Copyright (C) 2009 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Tests for the python and pyrex extensions of KnownGraph"""
27
from bzrlib.tests import test_graph
28
from bzrlib.revision import NULL_REVISION
31
def load_tests(standard_tests, module, loader):
32
"""Parameterize tests for all versions of groupcompress."""
34
('python', {'module': _known_graph_py, 'do_cache': True}),
37
('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
39
suite = loader.suiteClass()
40
if CompiledKnownGraphFeature.available():
41
from bzrlib import _known_graph_pyx
42
scenarios.append(('C', {'module': _known_graph_pyx, 'do_cache': True}))
43
caching_scenarios.append(('C-nocache',
44
{'module': _known_graph_pyx, 'do_cache': False}))
46
# the compiled module isn't available, so we add a failing test
47
class FailWithoutFeature(tests.TestCase):
49
self.requireFeature(CompiledKnownGraphFeature)
50
suite.addTest(loader.loadTestsFromTestCase(FailWithoutFeature))
51
# TestKnownGraphHeads needs to be permutated with and without caching.
52
# All other TestKnownGraph tests only need to be tested across module
53
heads_suite, other_suite = tests.split_suite_by_condition(
54
standard_tests, tests.condition_isinstance(TestKnownGraphHeads))
55
suite = tests.multiply_tests(other_suite, scenarios, suite)
56
suite = tests.multiply_tests(heads_suite, scenarios + caching_scenarios,
61
class _CompiledKnownGraphFeature(tests.Feature):
65
import bzrlib._known_graph_pyx
70
def feature_name(self):
71
return 'bzrlib._known_graph_pyx'
73
CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
83
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
86
class TestCaseWithKnownGraph(tests.TestCase):
88
module = None # Set by load_tests
90
def make_known_graph(self, ancestry):
91
return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
94
class TestKnownGraph(TestCaseWithKnownGraph):
96
def assertGDFO(self, graph, rev, gdfo):
97
node = graph._nodes[rev]
98
self.assertEqual(gdfo, node.gdfo)
100
def test_children_ancestry1(self):
101
graph = self.make_known_graph(test_graph.ancestry_1)
102
self.assertEqual(['rev1'], graph._nodes[NULL_REVISION].child_keys)
103
self.assertEqual(['rev2a', 'rev2b'],
104
sorted(graph._nodes['rev1'].child_keys))
105
self.assertEqual(['rev3'], sorted(graph._nodes['rev2a'].child_keys))
106
self.assertEqual(['rev4'], sorted(graph._nodes['rev3'].child_keys))
107
self.assertEqual(['rev4'], sorted(graph._nodes['rev2b'].child_keys))
109
def test_gdfo_ancestry_1(self):
110
graph = self.make_known_graph(test_graph.ancestry_1)
111
self.assertGDFO(graph, 'rev1', 2)
112
self.assertGDFO(graph, 'rev2b', 3)
113
self.assertGDFO(graph, 'rev2a', 3)
114
self.assertGDFO(graph, 'rev3', 4)
115
self.assertGDFO(graph, 'rev4', 5)
117
def test_gdfo_feature_branch(self):
118
graph = self.make_known_graph(test_graph.feature_branch)
119
self.assertGDFO(graph, 'rev1', 2)
120
self.assertGDFO(graph, 'rev2b', 3)
121
self.assertGDFO(graph, 'rev3b', 4)
123
def test_gdfo_extended_history_shortcut(self):
124
graph = self.make_known_graph(test_graph.extended_history_shortcut)
125
self.assertGDFO(graph, 'a', 2)
126
self.assertGDFO(graph, 'b', 3)
127
self.assertGDFO(graph, 'c', 4)
128
self.assertGDFO(graph, 'd', 5)
129
self.assertGDFO(graph, 'e', 6)
130
self.assertGDFO(graph, 'f', 6)
132
def test_gdfo_with_ghost(self):
133
graph = self.make_known_graph(test_graph.with_ghost)
134
self.assertGDFO(graph, 'f', 2)
135
self.assertGDFO(graph, 'e', 3)
136
self.assertGDFO(graph, 'g', 1)
137
self.assertGDFO(graph, 'b', 4)
138
self.assertGDFO(graph, 'd', 4)
139
self.assertGDFO(graph, 'a', 5)
140
self.assertGDFO(graph, 'c', 5)
143
class TestKnownGraphHeads(TestCaseWithKnownGraph):
145
do_cache = None # Set by load_tests
147
def test_heads_null(self):
148
graph = self.make_known_graph(test_graph.ancestry_1)
149
self.assertEqual(set(['null:']), graph.heads(['null:']))
150
self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
151
self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
152
self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
153
self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
155
def test_heads_one(self):
156
# A single node will always be a head
157
graph = self.make_known_graph(test_graph.ancestry_1)
158
self.assertEqual(set(['null:']), graph.heads(['null:']))
159
self.assertEqual(set(['rev1']), graph.heads(['rev1']))
160
self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
161
self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
162
self.assertEqual(set(['rev3']), graph.heads(['rev3']))
163
self.assertEqual(set(['rev4']), graph.heads(['rev4']))
165
def test_heads_single(self):
166
graph = self.make_known_graph(test_graph.ancestry_1)
167
self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
168
self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
169
self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
170
self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
171
self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
172
self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
173
self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
174
self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
175
self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
177
def test_heads_two_heads(self):
178
graph = self.make_known_graph(test_graph.ancestry_1)
179
self.assertEqual(set(['rev2a', 'rev2b']),
180
graph.heads(['rev2a', 'rev2b']))
181
self.assertEqual(set(['rev3', 'rev2b']),
182
graph.heads(['rev3', 'rev2b']))
184
def test_heads_criss_cross(self):
185
graph = self.make_known_graph(test_graph.criss_cross)
186
self.assertEqual(set(['rev2a']),
187
graph.heads(['rev2a', 'rev1']))
188
self.assertEqual(set(['rev2b']),
189
graph.heads(['rev2b', 'rev1']))
190
self.assertEqual(set(['rev3a']),
191
graph.heads(['rev3a', 'rev1']))
192
self.assertEqual(set(['rev3b']),
193
graph.heads(['rev3b', 'rev1']))
194
self.assertEqual(set(['rev2a', 'rev2b']),
195
graph.heads(['rev2a', 'rev2b']))
196
self.assertEqual(set(['rev3a']),
197
graph.heads(['rev3a', 'rev2a']))
198
self.assertEqual(set(['rev3a']),
199
graph.heads(['rev3a', 'rev2b']))
200
self.assertEqual(set(['rev3a']),
201
graph.heads(['rev3a', 'rev2a', 'rev2b']))
202
self.assertEqual(set(['rev3b']),
203
graph.heads(['rev3b', 'rev2a']))
204
self.assertEqual(set(['rev3b']),
205
graph.heads(['rev3b', 'rev2b']))
206
self.assertEqual(set(['rev3b']),
207
graph.heads(['rev3b', 'rev2a', 'rev2b']))
208
self.assertEqual(set(['rev3a', 'rev3b']),
209
graph.heads(['rev3a', 'rev3b']))
210
self.assertEqual(set(['rev3a', 'rev3b']),
211
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
213
def test_heads_shortcut(self):
214
graph = self.make_known_graph(test_graph.history_shortcut)
215
self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
216
graph.heads(['rev2a', 'rev2b', 'rev2c']))
217
self.assertEqual(set(['rev3a', 'rev3b']),
218
graph.heads(['rev3a', 'rev3b']))
219
self.assertEqual(set(['rev3a', 'rev3b']),
220
graph.heads(['rev2a', 'rev3a', 'rev3b']))
221
self.assertEqual(set(['rev2a', 'rev3b']),
222
graph.heads(['rev2a', 'rev3b']))
223
self.assertEqual(set(['rev2c', 'rev3a']),
224
graph.heads(['rev2c', 'rev3a']))
226
def test_heads_linear(self):
227
graph = self.make_known_graph(test_graph.racing_shortcuts)
228
self.assertEqual(set(['w']), graph.heads(['w', 's']))
229
self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
230
self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
231
self.assertEqual(set(['z']), graph.heads(['s', 'z']))
233
def test_heads_alt_merge(self):
234
graph = self.make_known_graph(alt_merge)
235
self.assertEqual(set(['c']), graph.heads(['a', 'c']))
237
def test_heads_with_ghost(self):
238
graph = self.make_known_graph(test_graph.with_ghost)
239
self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
240
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
241
self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
242
self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
243
self.assertEqual(set(['c']), graph.heads(['c', 'g']))
244
self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
245
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
246
self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
249
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
251
def assertTopoSortOrder(self, ancestry):
252
"""Check topo_sort and iter_topo_order is genuinely topological order.
254
For every child in the graph, check if it comes after all of it's
257
graph = self.make_known_graph(ancestry)
258
sort_result = graph.topo_sort()
259
# We should have an entry in sort_result for every entry present in the
261
self.assertEqual(len(ancestry), len(sort_result))
262
node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
263
for node in sort_result:
264
parents = ancestry[node]
265
for parent in parents:
266
if parent not in ancestry:
269
if node_idx[node] <= node_idx[parent]:
270
self.fail("parent %s must come before child %s:\n%s"
271
% (parent, node, sort_result))
273
def test_topo_sort_empty(self):
274
"""TopoSort empty list"""
275
self.assertTopoSortOrder({})
277
def test_topo_sort_easy(self):
278
"""TopoSort list with one node"""
279
self.assertTopoSortOrder({0: []})
281
def test_topo_sort_cycle(self):
282
"""TopoSort traps graph with cycles"""
283
g = self.make_known_graph({0: [1],
285
self.assertRaises(errors.GraphCycleError, g.topo_sort)
287
def test_topo_sort_cycle_2(self):
288
"""TopoSort traps graph with longer cycle"""
289
g = self.make_known_graph({0: [1],
292
self.assertRaises(errors.GraphCycleError, g.topo_sort)
294
def test_topo_sort_cycle_with_tail(self):
295
"""TopoSort traps graph with longer cycle"""
296
g = self.make_known_graph({0: [1],
301
self.assertRaises(errors.GraphCycleError, g.topo_sort)
303
def test_topo_sort_1(self):
304
"""TopoSort simple nontrivial graph"""
305
self.assertTopoSortOrder({0: [3],
311
def test_topo_sort_partial(self):
312
"""Topological sort with partial ordering.
314
Multiple correct orderings are possible, so test for
315
correctness, not for exact match on the resulting list.
317
self.assertTopoSortOrder({0: [],
327
def test_topo_sort_ghost_parent(self):
328
"""Sort nodes, but don't include some parents in the output"""
329
self.assertTopoSortOrder({0: [1],
333
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
335
def assertSortAndIterate(self, ancestry, branch_tip, result_list):
336
"""Check that merge based sorting and iter_topo_order on graph works."""
337
graph = self.make_known_graph(ancestry)
338
value = graph.merge_sort(branch_tip)
339
value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
341
if result_list != value:
342
self.assertEqualDiff(pprint.pformat(result_list),
343
pprint.pformat(value))
345
def test_merge_sort_empty(self):
346
# sorting of an emptygraph does not error
347
self.assertSortAndIterate({}, None, [])
348
self.assertSortAndIterate({}, NULL_REVISION, [])
349
self.assertSortAndIterate({}, (NULL_REVISION,), [])
351
def test_merge_sort_not_empty_no_tip(self):
352
# merge sorting of a branch starting with None should result
353
# in an empty list: no revisions are dragged in.
354
self.assertSortAndIterate({0: []}, None, [])
355
self.assertSortAndIterate({0: []}, NULL_REVISION, [])
356
self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
358
def test_merge_sort_one_revision(self):
359
# sorting with one revision as the tip returns the correct fields:
360
# sequence - 0, revision id, merge depth - 0, end_of_merge
361
self.assertSortAndIterate({'id': []},
363
[('id', 0, (1,), True)])
365
def test_sequence_numbers_increase_no_merges(self):
366
# emit a few revisions with no merges to check the sequence
367
# numbering works in trivial cases
368
self.assertSortAndIterate(
373
[('C', 0, (3,), False),
374
('B', 0, (2,), False),
375
('A', 0, (1,), True),
379
def test_sequence_numbers_increase_with_merges(self):
380
# test that sequence numbers increase across merges
381
self.assertSortAndIterate(
386
[('C', 0, (2,), False),
387
('B', 1, (1,1,1), True),
388
('A', 0, (1,), True),
392
def test_merge_sort_race(self):
408
self.assertSortAndIterate(graph, 'F',
409
[('F', 0, (3,), False),
410
('D', 1, (2,2,1), False),
411
('C', 2, (2,1,1), True),
412
('B', 0, (2,), False),
413
('A', 0, (1,), True),
431
self.assertSortAndIterate(graph, 'F',
432
[('F', 0, (3,), False),
433
('D', 1, (2,1,2), False),
434
('C', 2, (2,2,1), True),
435
('X', 1, (2,1,1), True),
436
('B', 0, (2,), False),
437
('A', 0, (1,), True),
440
def test_merge_depth_with_nested_merges(self):
441
# the merge depth marker should reflect the depth of the revision
442
# in terms of merges out from the mainline
443
# revid, depth, parents:
452
self.assertSortAndIterate(
463
[('A', 0, (3,), False),
464
('B', 1, (1,3,2), False),
465
('C', 1, (1,3,1), True),
466
('D', 0, (2,), False),
467
('E', 1, (1,1,2), False),
468
('F', 2, (1,2,1), True),
469
('G', 1, (1,1,1), True),
470
('H', 0, (1,), True),
474
def test_dotted_revnos_with_simple_merges(self):
479
# D E F 3, 1.1.2, 1.2.1
481
# G H I 4, 1.2.2, 1.3.1
486
self.assertSortAndIterate(
501
[('L', 0, (6,), False),
502
('K', 1, (1,3,2), False),
503
('I', 1, (1,3,1), True),
504
('J', 0, (5,), False),
505
('H', 1, (1,2,2), False),
506
('F', 1, (1,2,1), True),
507
('G', 0, (4,), False),
508
('E', 1, (1,1,2), False),
509
('C', 1, (1,1,1), True),
510
('D', 0, (3,), False),
511
('B', 0, (2,), False),
512
('A', 0, (1,), True),
515
# Adding a shortcut from the first revision should not change any of
516
# the existing numbers
517
self.assertSortAndIterate(
534
[('N', 0, (7,), False),
535
('M', 1, (1,4,1), True),
536
('L', 0, (6,), False),
537
('K', 1, (1,3,2), False),
538
('I', 1, (1,3,1), True),
539
('J', 0, (5,), False),
540
('H', 1, (1,2,2), False),
541
('F', 1, (1,2,1), True),
542
('G', 0, (4,), False),
543
('E', 1, (1,1,2), False),
544
('C', 1, (1,1,1), True),
545
('D', 0, (3,), False),
546
('B', 0, (2,), False),
547
('A', 0, (1,), True),
551
def test_end_of_merge_not_last_revision_in_branch(self):
552
# within a branch only the last revision gets an
553
# end of merge marker.
554
self.assertSortAndIterate(
559
[('A', 0, (2,), False),
564
def test_end_of_merge_multiple_revisions_merged_at_once(self):
565
# when multiple branches are merged at once, both of their
566
# branch-endpoints should be listed as end-of-merge.
567
# Also, the order of the multiple merges should be
568
# left-right shown top to bottom.
569
# * means end of merge
578
self.assertSortAndIterate(
579
{'A': ['H', 'B', 'E'],
589
[('A', 0, (2,), False),
590
('B', 1, (1,3,2), False),
591
('C', 2, (1,4,1), True),
592
('D', 1, (1,3,1), True),
593
('E', 1, (1,1,2), False),
594
('F', 2, (1,2,1), True),
595
('G', 1, (1,1,1), True),
596
('H', 0, (1,), True),
600
def test_parallel_root_sequence_numbers_increase_with_merges(self):
601
"""When there are parallel roots, check their revnos."""
602
self.assertSortAndIterate(
607
[('C', 0, (2,), False),
608
('B', 1, (0,1,1), True),
609
('A', 0, (1,), True),
613
def test_revnos_are_globally_assigned(self):
614
"""revnos are assigned according to the revision they derive from."""
615
# in this test we setup a number of branches that all derive from
616
# the first revision, and then merge them one at a time, which
617
# should give the revisions as they merge numbers still deriving from
618
# the revision were based on.
619
# merge 3: J: ['G', 'I']
623
# merge 2: G: ['D', 'F']
627
# merge 1: D: ['A', 'C']
632
self.assertSortAndIterate(
645
[('J', 0, (4,), False),
646
('I', 1, (1,3,2), False),
647
('H', 1, (1,3,1), True),
648
('G', 0, (3,), False),
649
('F', 1, (1,2,2), False),
650
('E', 1, (1,2,1), True),
651
('D', 0, (2,), False),
652
('C', 1, (1,1,2), False),
653
('B', 1, (1,1,1), True),
654
('A', 0, (1,), True),
658
def test_roots_and_sub_branches_versus_ghosts(self):
659
"""Extra roots and their mini branches use the same numbering.
661
All of them use the 0-node numbering.
674
self.assertSortAndIterate(
695
[('R', 0, (6,), False),
696
('Q', 1, (0,4,5), False),
697
('P', 2, (0,6,1), True),
698
('O', 1, (0,4,4), False),
699
('N', 1, (0,4,3), False),
700
('M', 2, (0,5,1), True),
701
('L', 1, (0,4,2), False),
702
('K', 1, (0,4,1), True),
703
('J', 0, (5,), False),
704
('I', 1, (0,3,1), True),
705
('H', 0, (4,), False),
706
('G', 1, (0,1,3), False),
707
('F', 2, (0,2,1), True),
708
('E', 1, (0,1,2), False),
709
('D', 1, (0,1,1), True),
710
('C', 0, (3,), False),
711
('B', 0, (2,), False),
712
('A', 0, (1,), True),
716
def test_ghost(self):
717
# merge_sort should be able to ignore ghosts
723
self.assertSortAndIterate(
729
[('C', 0, (3,), False),
730
('B', 0, (2,), False),
731
('A', 0, (1,), True),
734
def test_graph_cycle(self):
735
# merge_sort should fail with a simple error when a graph cycle is
747
self.assertRaises(errors.GraphCycleError,
748
self.assertSortAndIterate,
added
removed
bzrlib/tests/test__known_graph.py
