← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

(jameinel) Allow 'bzr serve' to interpret SIGHUP as a graceful shutdown.
 (bug #795025) (John A Meinel)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
 
1
# Copyright (C) 2009, 2010, 2011 Canonical Ltd
 
2
#
 
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.
 
7
#
 
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.
 
12
#
 
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
 
16
 
 
17
"""Tests for the python and pyrex extensions of KnownGraph"""
 
18
 
 
19
import pprint
 
20
 
 
21
from bzrlib import (
 
22
    errors,
 
23
    _known_graph_py,
 
24
    tests,
 
25
    )
 
26
from bzrlib.tests import test_graph
 
27
from bzrlib.revision import NULL_REVISION
 
28
from bzrlib.tests.scenarios import load_tests_apply_scenarios
 
29
from bzrlib.tests import (
 
30
    features,
 
31
    )
 
32
 
 
33
 
 
34
def caching_scenarios():
 
35
    scenarios = [
 
36
        ('python', {'module': _known_graph_py, 'do_cache': True}),
 
37
    ]
 
38
    if compiled_known_graph_feature.available():
 
39
        scenarios.append(('C', {'module': compiled_known_graph_feature.module,
 
40
                                'do_cache': True}))
 
41
    return scenarios
 
42
 
 
43
 
 
44
def non_caching_scenarios():
 
45
    scenarios = [
 
46
        ('python-nocache', {'module': _known_graph_py, 'do_cache': False}),
 
47
    ]
 
48
    if compiled_known_graph_feature.available():
 
49
        scenarios.append(
 
50
            ('C-nocache', {'module': compiled_known_graph_feature.module,
 
51
                           'do_cache': False}))
 
52
    return scenarios
 
53
 
 
54
 
 
55
load_tests = load_tests_apply_scenarios
 
56
 
 
57
 
 
58
compiled_known_graph_feature = features.ModuleAvailableFeature(
 
59
    'bzrlib._known_graph_pyx')
 
60
 
 
61
 
 
62
#  a
 
63
#  |\
 
64
#  b |
 
65
#  | |
 
66
#  c |
 
67
#   \|
 
68
#    d
 
69
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
 
70
 
 
71
 
 
72
class TestCaseWithKnownGraph(tests.TestCase):
 
73
 
 
74
    scenarios = caching_scenarios()
 
75
    module = None # Set by load_tests
 
76
 
 
77
    def make_known_graph(self, ancestry):
 
78
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
 
79
 
 
80
 
 
81
class TestKnownGraph(TestCaseWithKnownGraph):
 
82
 
 
83
    def assertGDFO(self, graph, rev, gdfo):
 
84
        node = graph._nodes[rev]
 
85
        self.assertEqual(gdfo, node.gdfo)
 
86
 
 
87
    def test_children_ancestry1(self):
 
88
        graph = self.make_known_graph(test_graph.ancestry_1)
 
89
        self.assertEqual(['rev1'], graph.get_child_keys(NULL_REVISION))
 
90
        self.assertEqual(['rev2a', 'rev2b'],
 
91
                         sorted(graph.get_child_keys('rev1')))
 
92
        self.assertEqual(['rev3'], graph.get_child_keys('rev2a'))
 
93
        self.assertEqual(['rev4'], graph.get_child_keys('rev3'))
 
94
        self.assertEqual(['rev4'], graph.get_child_keys('rev2b'))
 
95
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
96
 
 
97
    def test_parent_ancestry1(self):
 
98
        graph = self.make_known_graph(test_graph.ancestry_1)
 
99
        self.assertEqual([NULL_REVISION], graph.get_parent_keys('rev1'))
 
100
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2a'))
 
101
        self.assertEqual(['rev1'], graph.get_parent_keys('rev2b'))
 
102
        self.assertEqual(['rev2a'], graph.get_parent_keys('rev3'))
 
103
        self.assertEqual(['rev2b', 'rev3'],
 
104
                         sorted(graph.get_parent_keys('rev4')))
 
105
        self.assertRaises(KeyError, graph.get_child_keys, 'not_in_graph')
 
106
    
 
107
    def test_parent_with_ghost(self):
 
108
        graph = self.make_known_graph(test_graph.with_ghost)
 
109
        self.assertEqual(None, graph.get_parent_keys('g'))
 
110
 
 
111
    def test_gdfo_ancestry_1(self):
 
112
        graph = self.make_known_graph(test_graph.ancestry_1)
 
113
        self.assertGDFO(graph, 'rev1', 2)
 
114
        self.assertGDFO(graph, 'rev2b', 3)
 
115
        self.assertGDFO(graph, 'rev2a', 3)
 
116
        self.assertGDFO(graph, 'rev3', 4)
 
117
        self.assertGDFO(graph, 'rev4', 5)
 
118
 
 
119
    def test_gdfo_feature_branch(self):
 
120
        graph = self.make_known_graph(test_graph.feature_branch)
 
121
        self.assertGDFO(graph, 'rev1', 2)
 
122
        self.assertGDFO(graph, 'rev2b', 3)
 
123
        self.assertGDFO(graph, 'rev3b', 4)
 
124
 
 
125
    def test_gdfo_extended_history_shortcut(self):
 
126
        graph = self.make_known_graph(test_graph.extended_history_shortcut)
 
127
        self.assertGDFO(graph, 'a', 2)
 
128
        self.assertGDFO(graph, 'b', 3)
 
129
        self.assertGDFO(graph, 'c', 4)
 
130
        self.assertGDFO(graph, 'd', 5)
 
131
        self.assertGDFO(graph, 'e', 6)
 
132
        self.assertGDFO(graph, 'f', 6)
 
133
 
 
134
    def test_gdfo_with_ghost(self):
 
135
        graph = self.make_known_graph(test_graph.with_ghost)
 
136
        self.assertGDFO(graph, 'f', 2)
 
137
        self.assertGDFO(graph, 'e', 3)
 
138
        self.assertGDFO(graph, 'g', 1)
 
139
        self.assertGDFO(graph, 'b', 4)
 
140
        self.assertGDFO(graph, 'd', 4)
 
141
        self.assertGDFO(graph, 'a', 5)
 
142
        self.assertGDFO(graph, 'c', 5)
 
143
 
 
144
    def test_add_existing_node(self):
 
145
        graph = self.make_known_graph(test_graph.ancestry_1)
 
146
        # Add a node that already exists with identical content
 
147
        # This is a 'no-op'
 
148
        self.assertGDFO(graph, 'rev4', 5)
 
149
        graph.add_node('rev4', ['rev3', 'rev2b'])
 
150
        self.assertGDFO(graph, 'rev4', 5)
 
151
        # This also works if we use a tuple rather than a list
 
152
        graph.add_node('rev4', ('rev3', 'rev2b'))
 
153
 
 
154
    def test_add_existing_node_mismatched_parents(self):
 
155
        graph = self.make_known_graph(test_graph.ancestry_1)
 
156
        self.assertRaises(ValueError, graph.add_node, 'rev4',
 
157
                          ['rev2b', 'rev3'])
 
158
 
 
159
    def test_add_node_with_ghost_parent(self):
 
160
        graph = self.make_known_graph(test_graph.ancestry_1)
 
161
        graph.add_node('rev5', ['rev2b', 'revGhost'])
 
162
        self.assertGDFO(graph, 'rev5', 4)
 
163
        self.assertGDFO(graph, 'revGhost', 1)
 
164
 
 
165
    def test_add_new_root(self):
 
166
        graph = self.make_known_graph(test_graph.ancestry_1)
 
167
        graph.add_node('rev5', [])
 
168
        self.assertGDFO(graph, 'rev5', 1)
 
169
 
 
170
    def test_add_with_all_ghost_parents(self):
 
171
        graph = self.make_known_graph(test_graph.ancestry_1)
 
172
        graph.add_node('rev5', ['ghost'])
 
173
        self.assertGDFO(graph, 'rev5', 2)
 
174
        self.assertGDFO(graph, 'ghost', 1)
 
175
 
 
176
    def test_gdfo_after_add_node(self):
 
177
        graph = self.make_known_graph(test_graph.ancestry_1)
 
178
        self.assertEqual([], graph.get_child_keys('rev4'))
 
179
        graph.add_node('rev5', ['rev4'])
 
180
        self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
 
181
        self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
 
182
        self.assertEqual([], graph.get_child_keys('rev5'))
 
183
        self.assertGDFO(graph, 'rev5', 6)
 
184
        graph.add_node('rev6', ['rev2b'])
 
185
        graph.add_node('rev7', ['rev6'])
 
186
        graph.add_node('rev8', ['rev7', 'rev5'])
 
187
        self.assertGDFO(graph, 'rev5', 6)
 
188
        self.assertGDFO(graph, 'rev6', 4)
 
189
        self.assertGDFO(graph, 'rev7', 5)
 
190
        self.assertGDFO(graph, 'rev8', 7)
 
191
 
 
192
    def test_fill_in_ghost(self):
 
193
        graph = self.make_known_graph(test_graph.with_ghost)
 
194
        # Add in a couple nodes and then fill in the 'ghost' so that it should
 
195
        # cause renumbering of children nodes
 
196
        graph.add_node('x', [])
 
197
        graph.add_node('y', ['x'])
 
198
        graph.add_node('z', ['y'])
 
199
        graph.add_node('g', ['z'])
 
200
        self.assertGDFO(graph, 'f', 2)
 
201
        self.assertGDFO(graph, 'e', 3)
 
202
        self.assertGDFO(graph, 'x', 1)
 
203
        self.assertGDFO(graph, 'y', 2)
 
204
        self.assertGDFO(graph, 'z', 3)
 
205
        self.assertGDFO(graph, 'g', 4)
 
206
        self.assertGDFO(graph, 'b', 4)
 
207
        self.assertGDFO(graph, 'd', 5)
 
208
        self.assertGDFO(graph, 'a', 5)
 
209
        self.assertGDFO(graph, 'c', 6)
 
210
 
 
211
 
 
212
class TestKnownGraphHeads(TestCaseWithKnownGraph):
 
213
 
 
214
    scenarios = caching_scenarios() + non_caching_scenarios()
 
215
    do_cache = None # Set by load_tests
 
216
 
 
217
    def test_heads_null(self):
 
218
        graph = self.make_known_graph(test_graph.ancestry_1)
 
219
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
220
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
221
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
222
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
223
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
224
 
 
225
    def test_heads_one(self):
 
226
        # A single node will always be a head
 
227
        graph = self.make_known_graph(test_graph.ancestry_1)
 
228
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
229
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
230
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
231
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
232
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
233
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
234
 
 
235
    def test_heads_single(self):
 
236
        graph = self.make_known_graph(test_graph.ancestry_1)
 
237
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
238
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
239
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
240
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
241
        self.assertEqual(set(['rev3']), graph.heads(['rev3', 'rev2a']))
 
242
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
243
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
244
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
245
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
246
 
 
247
    def test_heads_two_heads(self):
 
248
        graph = self.make_known_graph(test_graph.ancestry_1)
 
249
        self.assertEqual(set(['rev2a', 'rev2b']),
 
250
                         graph.heads(['rev2a', 'rev2b']))
 
251
        self.assertEqual(set(['rev3', 'rev2b']),
 
252
                         graph.heads(['rev3', 'rev2b']))
 
253
 
 
254
    def test_heads_criss_cross(self):
 
255
        graph = self.make_known_graph(test_graph.criss_cross)
 
256
        self.assertEqual(set(['rev2a']),
 
257
                         graph.heads(['rev2a', 'rev1']))
 
258
        self.assertEqual(set(['rev2b']),
 
259
                         graph.heads(['rev2b', 'rev1']))
 
260
        self.assertEqual(set(['rev3a']),
 
261
                         graph.heads(['rev3a', 'rev1']))
 
262
        self.assertEqual(set(['rev3b']),
 
263
                         graph.heads(['rev3b', 'rev1']))
 
264
        self.assertEqual(set(['rev2a', 'rev2b']),
 
265
                         graph.heads(['rev2a', 'rev2b']))
 
266
        self.assertEqual(set(['rev3a']),
 
267
                         graph.heads(['rev3a', 'rev2a']))
 
268
        self.assertEqual(set(['rev3a']),
 
269
                         graph.heads(['rev3a', 'rev2b']))
 
270
        self.assertEqual(set(['rev3a']),
 
271
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
272
        self.assertEqual(set(['rev3b']),
 
273
                         graph.heads(['rev3b', 'rev2a']))
 
274
        self.assertEqual(set(['rev3b']),
 
275
                         graph.heads(['rev3b', 'rev2b']))
 
276
        self.assertEqual(set(['rev3b']),
 
277
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
278
        self.assertEqual(set(['rev3a', 'rev3b']),
 
279
                         graph.heads(['rev3a', 'rev3b']))
 
280
        self.assertEqual(set(['rev3a', 'rev3b']),
 
281
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
282
 
 
283
    def test_heads_shortcut(self):
 
284
        graph = self.make_known_graph(test_graph.history_shortcut)
 
285
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
286
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
287
        self.assertEqual(set(['rev3a', 'rev3b']),
 
288
                         graph.heads(['rev3a', 'rev3b']))
 
289
        self.assertEqual(set(['rev3a', 'rev3b']),
 
290
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
291
        self.assertEqual(set(['rev2a', 'rev3b']),
 
292
                         graph.heads(['rev2a', 'rev3b']))
 
293
        self.assertEqual(set(['rev2c', 'rev3a']),
 
294
                         graph.heads(['rev2c', 'rev3a']))
 
295
 
 
296
    def test_heads_linear(self):
 
297
        graph = self.make_known_graph(test_graph.racing_shortcuts)
 
298
        self.assertEqual(set(['w']), graph.heads(['w', 's']))
 
299
        self.assertEqual(set(['z']), graph.heads(['w', 's', 'z']))
 
300
        self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
 
301
        self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
302
 
 
303
    def test_heads_alt_merge(self):
 
304
        graph = self.make_known_graph(alt_merge)
 
305
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
 
306
 
 
307
    def test_heads_with_ghost(self):
 
308
        graph = self.make_known_graph(test_graph.with_ghost)
 
309
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
310
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c']))
 
311
        self.assertEqual(set(['a', 'g']), graph.heads(['a', 'g']))
 
312
        self.assertEqual(set(['f', 'g']), graph.heads(['f', 'g']))
 
313
        self.assertEqual(set(['c']), graph.heads(['c', 'g']))
 
314
        self.assertEqual(set(['c']), graph.heads(['c', 'b', 'd', 'g']))
 
315
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'e', 'g']))
 
316
        self.assertEqual(set(['a', 'c']), graph.heads(['a', 'c', 'f']))
 
317
 
 
318
    def test_filling_in_ghosts_resets_head_cache(self):
 
319
        graph = self.make_known_graph(test_graph.with_ghost)
 
320
        self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))
 
321
        # 'g' is filled in, and decends from 'e', so the heads result is now
 
322
        # different
 
323
        graph.add_node('g', ['e'])
 
324
        self.assertEqual(set(['g']), graph.heads(['e', 'g']))
 
325
 
 
326
 
 
327
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
 
328
 
 
329
    def assertTopoSortOrder(self, ancestry):
 
330
        """Check topo_sort and iter_topo_order is genuinely topological order.
 
331
 
 
332
        For every child in the graph, check if it comes after all of it's
 
333
        parents.
 
334
        """
 
335
        graph = self.make_known_graph(ancestry)
 
336
        sort_result = graph.topo_sort()
 
337
        # We should have an entry in sort_result for every entry present in the
 
338
        # graph.
 
339
        self.assertEqual(len(ancestry), len(sort_result))
 
340
        node_idx = dict((node, idx) for idx, node in enumerate(sort_result))
 
341
        for node in sort_result:
 
342
            parents = ancestry[node]
 
343
            for parent in parents:
 
344
                if parent not in ancestry:
 
345
                    # ghost
 
346
                    continue
 
347
                if node_idx[node] <= node_idx[parent]:
 
348
                    self.fail("parent %s must come before child %s:\n%s"
 
349
                              % (parent, node, sort_result))
 
350
 
 
351
    def test_topo_sort_empty(self):
 
352
        """TopoSort empty list"""
 
353
        self.assertTopoSortOrder({})
 
354
 
 
355
    def test_topo_sort_easy(self):
 
356
        """TopoSort list with one node"""
 
357
        self.assertTopoSortOrder({0: []})
 
358
 
 
359
    def test_topo_sort_cycle(self):
 
360
        """TopoSort traps graph with cycles"""
 
361
        g = self.make_known_graph({0: [1],
 
362
                                  1: [0]})
 
363
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
364
 
 
365
    def test_topo_sort_cycle_2(self):
 
366
        """TopoSort traps graph with longer cycle"""
 
367
        g = self.make_known_graph({0: [1],
 
368
                                   1: [2],
 
369
                                   2: [0]})
 
370
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
371
 
 
372
    def test_topo_sort_cycle_with_tail(self):
 
373
        """TopoSort traps graph with longer cycle"""
 
374
        g = self.make_known_graph({0: [1],
 
375
                                   1: [2],
 
376
                                   2: [3, 4],
 
377
                                   3: [0],
 
378
                                   4: []})
 
379
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
380
 
 
381
    def test_topo_sort_1(self):
 
382
        """TopoSort simple nontrivial graph"""
 
383
        self.assertTopoSortOrder({0: [3],
 
384
                                  1: [4],
 
385
                                  2: [1, 4],
 
386
                                  3: [],
 
387
                                  4: [0, 3]})
 
388
 
 
389
    def test_topo_sort_partial(self):
 
390
        """Topological sort with partial ordering.
 
391
 
 
392
        Multiple correct orderings are possible, so test for
 
393
        correctness, not for exact match on the resulting list.
 
394
        """
 
395
        self.assertTopoSortOrder({0: [],
 
396
                                  1: [0],
 
397
                                  2: [0],
 
398
                                  3: [0],
 
399
                                  4: [1, 2, 3],
 
400
                                  5: [1, 2],
 
401
                                  6: [1, 2],
 
402
                                  7: [2, 3],
 
403
                                  8: [0, 1, 4, 5, 6]})
 
404
 
 
405
    def test_topo_sort_ghost_parent(self):
 
406
        """Sort nodes, but don't include some parents in the output"""
 
407
        self.assertTopoSortOrder({0: [1],
 
408
                                  1: [2]})
 
409
 
 
410
 
 
411
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
 
412
 
 
413
    def assertSortAndIterate(self, ancestry, branch_tip, result_list):
 
414
        """Check that merge based sorting and iter_topo_order on graph works."""
 
415
        graph = self.make_known_graph(ancestry)
 
416
        value = graph.merge_sort(branch_tip)
 
417
        value = [(n.key, n.merge_depth, n.revno, n.end_of_merge)
 
418
                 for n in value]
 
419
        if result_list != value:
 
420
            self.assertEqualDiff(pprint.pformat(result_list),
 
421
                                 pprint.pformat(value))
 
422
 
 
423
    def test_merge_sort_empty(self):
 
424
        # sorting of an emptygraph does not error
 
425
        self.assertSortAndIterate({}, None, [])
 
426
        self.assertSortAndIterate({}, NULL_REVISION, [])
 
427
        self.assertSortAndIterate({}, (NULL_REVISION,), [])
 
428
 
 
429
    def test_merge_sort_not_empty_no_tip(self):
 
430
        # merge sorting of a branch starting with None should result
 
431
        # in an empty list: no revisions are dragged in.
 
432
        self.assertSortAndIterate({0: []}, None, [])
 
433
        self.assertSortAndIterate({0: []}, NULL_REVISION, [])
 
434
        self.assertSortAndIterate({0: []}, (NULL_REVISION,), [])
 
435
 
 
436
    def test_merge_sort_one_revision(self):
 
437
        # sorting with one revision as the tip returns the correct fields:
 
438
        # sequence - 0, revision id, merge depth - 0, end_of_merge
 
439
        self.assertSortAndIterate({'id': []},
 
440
                                  'id',
 
441
                                  [('id', 0, (1,), True)])
 
442
 
 
443
    def test_sequence_numbers_increase_no_merges(self):
 
444
        # emit a few revisions with no merges to check the sequence
 
445
        # numbering works in trivial cases
 
446
        self.assertSortAndIterate(
 
447
            {'A': [],
 
448
             'B': ['A'],
 
449
             'C': ['B']},
 
450
            'C',
 
451
            [('C', 0, (3,), False),
 
452
             ('B', 0, (2,), False),
 
453
             ('A', 0, (1,), True),
 
454
             ],
 
455
            )
 
456
 
 
457
    def test_sequence_numbers_increase_with_merges(self):
 
458
        # test that sequence numbers increase across merges
 
459
        self.assertSortAndIterate(
 
460
            {'A': [],
 
461
             'B': ['A'],
 
462
             'C': ['A', 'B']},
 
463
            'C',
 
464
            [('C', 0, (2,), False),
 
465
             ('B', 1, (1,1,1), True),
 
466
             ('A', 0, (1,), True),
 
467
             ],
 
468
            )
 
469
 
 
470
    def test_merge_sort_race(self):
 
471
        # A
 
472
        # |
 
473
        # B-.
 
474
        # |\ \
 
475
        # | | C
 
476
        # | |/
 
477
        # | D
 
478
        # |/
 
479
        # F
 
480
        graph = {'A': [],
 
481
                 'B': ['A'],
 
482
                 'C': ['B'],
 
483
                 'D': ['B', 'C'],
 
484
                 'F': ['B', 'D'],
 
485
                 }
 
486
        self.assertSortAndIterate(graph, 'F',
 
487
            [('F', 0, (3,), False),
 
488
             ('D', 1, (2,2,1), False),
 
489
             ('C', 2, (2,1,1), True),
 
490
             ('B', 0, (2,), False),
 
491
             ('A', 0, (1,), True),
 
492
             ])
 
493
        # A
 
494
        # |
 
495
        # B-.
 
496
        # |\ \
 
497
        # | X C
 
498
        # | |/
 
499
        # | D
 
500
        # |/
 
501
        # F
 
502
        graph = {'A': [],
 
503
                 'B': ['A'],
 
504
                 'C': ['B'],
 
505
                 'X': ['B'],
 
506
                 'D': ['X', 'C'],
 
507
                 'F': ['B', 'D'],
 
508
                 }
 
509
        self.assertSortAndIterate(graph, 'F',
 
510
            [('F', 0, (3,), False),
 
511
             ('D', 1, (2,1,2), False),
 
512
             ('C', 2, (2,2,1), True),
 
513
             ('X', 1, (2,1,1), True),
 
514
             ('B', 0, (2,), False),
 
515
             ('A', 0, (1,), True),
 
516
             ])
 
517
 
 
518
    def test_merge_depth_with_nested_merges(self):
 
519
        # the merge depth marker should reflect the depth of the revision
 
520
        # in terms of merges out from the mainline
 
521
        # revid, depth, parents:
 
522
        #  A 0   [D, B]
 
523
        #  B  1  [C, F]
 
524
        #  C  1  [H]
 
525
        #  D 0   [H, E]
 
526
        #  E  1  [G, F]
 
527
        #  F   2 [G]
 
528
        #  G  1  [H]
 
529
        #  H 0
 
530
        self.assertSortAndIterate(
 
531
            {'A': ['D', 'B'],
 
532
             'B': ['C', 'F'],
 
533
             'C': ['H'],
 
534
             'D': ['H', 'E'],
 
535
             'E': ['G', 'F'],
 
536
             'F': ['G'],
 
537
             'G': ['H'],
 
538
             'H': []
 
539
             },
 
540
            'A',
 
541
            [('A', 0, (3,),  False),
 
542
             ('B', 1, (1,3,2), False),
 
543
             ('C', 1, (1,3,1), True),
 
544
             ('D', 0, (2,), False),
 
545
             ('E', 1, (1,1,2), False),
 
546
             ('F', 2, (1,2,1), True),
 
547
             ('G', 1, (1,1,1), True),
 
548
             ('H', 0, (1,), True),
 
549
             ],
 
550
            )
 
551
 
 
552
    def test_dotted_revnos_with_simple_merges(self):
 
553
        # A         1
 
554
        # |\
 
555
        # B C       2, 1.1.1
 
556
        # | |\
 
557
        # D E F     3, 1.1.2, 1.2.1
 
558
        # |/ /|
 
559
        # G H I     4, 1.2.2, 1.3.1
 
560
        # |/ /
 
561
        # J K       5, 1.3.2
 
562
        # |/
 
563
        # L         6
 
564
        self.assertSortAndIterate(
 
565
            {'A': [],
 
566
             'B': ['A'],
 
567
             'C': ['A'],
 
568
             'D': ['B'],
 
569
             'E': ['C'],
 
570
             'F': ['C'],
 
571
             'G': ['D', 'E'],
 
572
             'H': ['F'],
 
573
             'I': ['F'],
 
574
             'J': ['G', 'H'],
 
575
             'K': ['I'],
 
576
             'L': ['J', 'K'],
 
577
            },
 
578
            'L',
 
579
            [('L', 0, (6,), False),
 
580
             ('K', 1, (1,3,2), False),
 
581
             ('I', 1, (1,3,1), True),
 
582
             ('J', 0, (5,), False),
 
583
             ('H', 1, (1,2,2), False),
 
584
             ('F', 1, (1,2,1), True),
 
585
             ('G', 0, (4,), False),
 
586
             ('E', 1, (1,1,2), False),
 
587
             ('C', 1, (1,1,1), True),
 
588
             ('D', 0, (3,), False),
 
589
             ('B', 0, (2,), False),
 
590
             ('A', 0, (1,),  True),
 
591
             ],
 
592
            )
 
593
        # Adding a shortcut from the first revision should not change any of
 
594
        # the existing numbers
 
595
        self.assertSortAndIterate(
 
596
            {'A': [],
 
597
             'B': ['A'],
 
598
             'C': ['A'],
 
599
             'D': ['B'],
 
600
             'E': ['C'],
 
601
             'F': ['C'],
 
602
             'G': ['D', 'E'],
 
603
             'H': ['F'],
 
604
             'I': ['F'],
 
605
             'J': ['G', 'H'],
 
606
             'K': ['I'],
 
607
             'L': ['J', 'K'],
 
608
             'M': ['A'],
 
609
             'N': ['L', 'M'],
 
610
            },
 
611
            'N',
 
612
            [('N', 0, (7,), False),
 
613
             ('M', 1, (1,4,1), True),
 
614
             ('L', 0, (6,), False),
 
615
             ('K', 1, (1,3,2), False),
 
616
             ('I', 1, (1,3,1), True),
 
617
             ('J', 0, (5,), False),
 
618
             ('H', 1, (1,2,2), False),
 
619
             ('F', 1, (1,2,1), True),
 
620
             ('G', 0, (4,), False),
 
621
             ('E', 1, (1,1,2), False),
 
622
             ('C', 1, (1,1,1), True),
 
623
             ('D', 0, (3,), False),
 
624
             ('B', 0, (2,), False),
 
625
             ('A', 0, (1,),  True),
 
626
             ],
 
627
            )
 
628
 
 
629
    def test_end_of_merge_not_last_revision_in_branch(self):
 
630
        # within a branch only the last revision gets an
 
631
        # end of merge marker.
 
632
        self.assertSortAndIterate(
 
633
            {'A': ['B'],
 
634
             'B': [],
 
635
             },
 
636
            'A',
 
637
            [('A', 0, (2,), False),
 
638
             ('B', 0, (1,), True)
 
639
             ],
 
640
            )
 
641
 
 
642
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
 
643
        # when multiple branches are merged at once, both of their
 
644
        # branch-endpoints should be listed as end-of-merge.
 
645
        # Also, the order of the multiple merges should be
 
646
        # left-right shown top to bottom.
 
647
        # * means end of merge
 
648
        # A 0    [H, B, E]
 
649
        # B  1   [D, C]
 
650
        # C   2  [D]       *
 
651
        # D  1   [H]       *
 
652
        # E  1   [G, F]
 
653
        # F   2  [G]       *
 
654
        # G  1   [H]       *
 
655
        # H 0    []        *
 
656
        self.assertSortAndIterate(
 
657
            {'A': ['H', 'B', 'E'],
 
658
             'B': ['D', 'C'],
 
659
             'C': ['D'],
 
660
             'D': ['H'],
 
661
             'E': ['G', 'F'],
 
662
             'F': ['G'],
 
663
             'G': ['H'],
 
664
             'H': [],
 
665
             },
 
666
            'A',
 
667
            [('A', 0, (2,), False),
 
668
             ('B', 1, (1,3,2), False),
 
669
             ('C', 2, (1,4,1), True),
 
670
             ('D', 1, (1,3,1), True),
 
671
             ('E', 1, (1,1,2), False),
 
672
             ('F', 2, (1,2,1), True),
 
673
             ('G', 1, (1,1,1), True),
 
674
             ('H', 0, (1,), True),
 
675
             ],
 
676
            )
 
677
 
 
678
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
 
679
        """When there are parallel roots, check their revnos."""
 
680
        self.assertSortAndIterate(
 
681
            {'A': [],
 
682
             'B': [],
 
683
             'C': ['A', 'B']},
 
684
            'C',
 
685
            [('C', 0, (2,), False),
 
686
             ('B', 1, (0,1,1), True),
 
687
             ('A', 0, (1,), True),
 
688
             ],
 
689
            )
 
690
 
 
691
    def test_revnos_are_globally_assigned(self):
 
692
        """revnos are assigned according to the revision they derive from."""
 
693
        # in this test we setup a number of branches that all derive from
 
694
        # the first revision, and then merge them one at a time, which
 
695
        # should give the revisions as they merge numbers still deriving from
 
696
        # the revision were based on.
 
697
        # merge 3: J: ['G', 'I']
 
698
        # branch 3:
 
699
        #  I: ['H']
 
700
        #  H: ['A']
 
701
        # merge 2: G: ['D', 'F']
 
702
        # branch 2:
 
703
        #  F: ['E']
 
704
        #  E: ['A']
 
705
        # merge 1: D: ['A', 'C']
 
706
        # branch 1:
 
707
        #  C: ['B']
 
708
        #  B: ['A']
 
709
        # root: A: []
 
710
        self.assertSortAndIterate(
 
711
            {'J': ['G', 'I'],
 
712
             'I': ['H',],
 
713
             'H': ['A'],
 
714
             'G': ['D', 'F'],
 
715
             'F': ['E'],
 
716
             'E': ['A'],
 
717
             'D': ['A', 'C'],
 
718
             'C': ['B'],
 
719
             'B': ['A'],
 
720
             'A': [],
 
721
             },
 
722
            'J',
 
723
            [('J', 0, (4,), False),
 
724
             ('I', 1, (1,3,2), False),
 
725
             ('H', 1, (1,3,1), True),
 
726
             ('G', 0, (3,), False),
 
727
             ('F', 1, (1,2,2), False),
 
728
             ('E', 1, (1,2,1), True),
 
729
             ('D', 0, (2,), False),
 
730
             ('C', 1, (1,1,2), False),
 
731
             ('B', 1, (1,1,1), True),
 
732
             ('A', 0, (1,), True),
 
733
             ],
 
734
            )
 
735
 
 
736
    def test_roots_and_sub_branches_versus_ghosts(self):
 
737
        """Extra roots and their mini branches use the same numbering.
 
738
 
 
739
        All of them use the 0-node numbering.
 
740
        """
 
741
        #       A D   K
 
742
        #       | |\  |\
 
743
        #       B E F L M
 
744
        #       | |/  |/
 
745
        #       C G   N
 
746
        #       |/    |\
 
747
        #       H I   O P
 
748
        #       |/    |/
 
749
        #       J     Q
 
750
        #       |.---'
 
751
        #       R
 
752
        self.assertSortAndIterate(
 
753
            {'A': [],
 
754
             'B': ['A'],
 
755
             'C': ['B'],
 
756
             'D': [],
 
757
             'E': ['D'],
 
758
             'F': ['D'],
 
759
             'G': ['E', 'F'],
 
760
             'H': ['C', 'G'],
 
761
             'I': [],
 
762
             'J': ['H', 'I'],
 
763
             'K': [],
 
764
             'L': ['K'],
 
765
             'M': ['K'],
 
766
             'N': ['L', 'M'],
 
767
             'O': ['N'],
 
768
             'P': ['N'],
 
769
             'Q': ['O', 'P'],
 
770
             'R': ['J', 'Q'],
 
771
            },
 
772
            'R',
 
773
            [('R', 0, (6,), False),
 
774
             ('Q', 1, (0,4,5), False),
 
775
             ('P', 2, (0,6,1), True),
 
776
             ('O', 1, (0,4,4), False),
 
777
             ('N', 1, (0,4,3), False),
 
778
             ('M', 2, (0,5,1), True),
 
779
             ('L', 1, (0,4,2), False),
 
780
             ('K', 1, (0,4,1), True),
 
781
             ('J', 0, (5,), False),
 
782
             ('I', 1, (0,3,1), True),
 
783
             ('H', 0, (4,), False),
 
784
             ('G', 1, (0,1,3), False),
 
785
             ('F', 2, (0,2,1), True),
 
786
             ('E', 1, (0,1,2), False),
 
787
             ('D', 1, (0,1,1), True),
 
788
             ('C', 0, (3,), False),
 
789
             ('B', 0, (2,), False),
 
790
             ('A', 0, (1,), True),
 
791
             ],
 
792
            )
 
793
 
 
794
    def test_ghost(self):
 
795
        # merge_sort should be able to ignore ghosts
 
796
        # A
 
797
        # |
 
798
        # B ghost
 
799
        # |/
 
800
        # C
 
801
        self.assertSortAndIterate(
 
802
            {'A': [],
 
803
             'B': ['A'],
 
804
             'C': ['B', 'ghost'],
 
805
            },
 
806
            'C',
 
807
            [('C', 0, (3,), False),
 
808
             ('B', 0, (2,), False),
 
809
             ('A', 0, (1,), True),
 
810
            ])
 
811
 
 
812
    def test_lefthand_ghost(self):
 
813
        # ghost
 
814
        #  |
 
815
        #  A
 
816
        #  |
 
817
        #  B
 
818
        self.assertSortAndIterate(
 
819
            {'A': ['ghost'],
 
820
             'B': ['A'],
 
821
            }, 'B',
 
822
            [('B', 0, (2,), False),
 
823
             ('A', 0, (1,), True),
 
824
            ])
 
825
 
 
826
    def test_graph_cycle(self):
 
827
        # merge_sort should fail with a simple error when a graph cycle is
 
828
        # encountered.
 
829
        #
 
830
        # A
 
831
        # |,-.
 
832
        # B  |
 
833
        # |  |
 
834
        # C  ^
 
835
        # |  |
 
836
        # D  |
 
837
        # |'-'
 
838
        # E
 
839
        self.assertRaises(errors.GraphCycleError,
 
840
            self.assertSortAndIterate,
 
841
                {'A': [],
 
842
                 'B': ['D'],
 
843
                 'C': ['B'],
 
844
                 'D': ['C'],
 
845
                 'E': ['D'],
 
846
                },
 
847
                'E',
 
848
                [])
 
849
 
 
850
 
 
851
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
852
    """Test the sort order returned by gc_sort."""
 
853
 
 
854
    def assertSorted(self, expected, parent_map):
 
855
        graph = self.make_known_graph(parent_map)
 
856
        value = graph.gc_sort()
 
857
        if expected != value:
 
858
            self.assertEqualDiff(pprint.pformat(expected),
 
859
                                 pprint.pformat(value))
 
860
 
 
861
    def test_empty(self):
 
862
        self.assertSorted([], {})
 
863
 
 
864
    def test_single(self):
 
865
        self.assertSorted(['a'], {'a':()})
 
866
        self.assertSorted([('a',)], {('a',):()})
 
867
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
868
 
 
869
    def test_linear(self):
 
870
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
871
        self.assertSorted([('c',), ('b',), ('a',)],
 
872
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
873
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
874
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
875
                           ('F', 'c'): (('F', 'b'),)})
 
876
 
 
877
    def test_mixed_ancestries(self):
 
878
        # Each prefix should be sorted separately
 
879
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
880
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
881
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
882
                          ],
 
883
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
884
                           ('F', 'c'): (('F', 'b'),),
 
885
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
886
                           ('G', 'c'): (('G', 'b'),),
 
887
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
888
                           ('Q', 'c'): (('Q', 'b'),),
 
889
                          })
 
890
 
 
891
    def test_stable_sorting(self):
 
892
        # the sort order should be stable even when extra nodes are added
 
893
        self.assertSorted(['b', 'c', 'a'],
 
894
                          {'a':(), 'b':('a',), 'c':('a',)})
 
895
        self.assertSorted(['b', 'c', 'd', 'a'],
 
896
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
897
        self.assertSorted(['b', 'c', 'd', 'a'],
 
898
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
899
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
900
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
901
                           'Z':('a',)})
 
902
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
903
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
904
                           'Z':('a',),
 
905
                           'e':('b', 'c', 'd'),
 
906
                           'f':('d', 'Z'),
 
907
                           })
 
908
 
 
909
    def test_skip_ghost(self):
 
910
        self.assertSorted(['b', 'c', 'a'],
 
911
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
912
 
 
913
    def test_skip_mainline_ghost(self):
 
914
        self.assertSorted(['b', 'c', 'a'],
 
915
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})