← 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

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-01-21 10:00:42 UTC
  • mfrom: (4978.1.2 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100121100042-77858a88k2zpec7b
(nmb) Add documentation for multi-parent merges

Show diffs side-by-side

added added

removed removed

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