← 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: John Arbash Meinel
  • Date: 2010-01-13 16:23:07 UTC
  • mto: (4634.119.7 2.0)
  • mto: This revision was merged to the branch mainline in revision 4959.
  • Revision ID: john@arbash-meinel.com-20100113162307-0bs82td16gzih827
Update the MANIFEST.in file.

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 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}))
 
45
    else:
 
46
        # the compiled module isn't available, so we add a failing test
 
47
        class FailWithoutFeature(tests.TestCase):
 
48
            def test_fail(self):
 
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,
 
57
                                 suite)
 
58
    return suite
 
59
 
 
60
 
 
61
class _CompiledKnownGraphFeature(tests.Feature):
 
62
 
 
63
    def _probe(self):
 
64
        try:
 
65
            import bzrlib._known_graph_pyx
 
66
        except ImportError:
 
67
            return False
 
68
        return True
 
69
 
 
70
    def feature_name(self):
 
71
        return 'bzrlib._known_graph_pyx'
 
72
 
 
73
CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
 
74
 
 
75
 
 
76
#  a
 
77
#  |\
 
78
#  b |
 
79
#  | |
 
80
#  c |
 
81
#   \|
 
82
#    d
 
83
alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
 
84
 
 
85
 
 
86
class TestCaseWithKnownGraph(tests.TestCase):
 
87
 
 
88
    module = None # Set by load_tests
 
89
 
 
90
    def make_known_graph(self, ancestry):
 
91
        return self.module.KnownGraph(ancestry, do_cache=self.do_cache)
 
92
 
 
93
 
 
94
class TestKnownGraph(TestCaseWithKnownGraph):
 
95
 
 
96
    def assertGDFO(self, graph, rev, gdfo):
 
97
        node = graph._nodes[rev]
 
98
        self.assertEqual(gdfo, node.gdfo)
 
99
 
 
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))
 
108
 
 
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)
 
116
 
 
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)
 
122
 
 
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)
 
131
 
 
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)
 
141
 
 
142
 
 
143
class TestKnownGraphHeads(TestCaseWithKnownGraph):
 
144
 
 
145
    do_cache = None # Set by load_tests
 
146
 
 
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:')))
 
154
 
 
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']))
 
164
 
 
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']))
 
176
 
 
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']))
 
183
 
 
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']))
 
212
 
 
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']))
 
225
 
 
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']))
 
232
 
 
233
    def test_heads_alt_merge(self):
 
234
        graph = self.make_known_graph(alt_merge)
 
235
        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
 
236
 
 
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']))
 
247
 
 
248
 
 
249
class TestKnownGraphTopoSort(TestCaseWithKnownGraph):
 
250
 
 
251
    def assertTopoSortOrder(self, ancestry):
 
252
        """Check topo_sort and iter_topo_order is genuinely topological order.
 
253
 
 
254
        For every child in the graph, check if it comes after all of it's
 
255
        parents.
 
256
        """
 
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
 
260
        # graph.
 
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:
 
267
                    # ghost
 
268
                    continue
 
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))
 
272
 
 
273
    def test_topo_sort_empty(self):
 
274
        """TopoSort empty list"""
 
275
        self.assertTopoSortOrder({})
 
276
 
 
277
    def test_topo_sort_easy(self):
 
278
        """TopoSort list with one node"""
 
279
        self.assertTopoSortOrder({0: []})
 
280
 
 
281
    def test_topo_sort_cycle(self):
 
282
        """TopoSort traps graph with cycles"""
 
283
        g = self.make_known_graph({0: [1],
 
284
                                  1: [0]})
 
285
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
286
 
 
287
    def test_topo_sort_cycle_2(self):
 
288
        """TopoSort traps graph with longer cycle"""
 
289
        g = self.make_known_graph({0: [1],
 
290
                                   1: [2],
 
291
                                   2: [0]})
 
292
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
293
 
 
294
    def test_topo_sort_cycle_with_tail(self):
 
295
        """TopoSort traps graph with longer cycle"""
 
296
        g = self.make_known_graph({0: [1],
 
297
                                   1: [2],
 
298
                                   2: [3, 4],
 
299
                                   3: [0],
 
300
                                   4: []})
 
301
        self.assertRaises(errors.GraphCycleError, g.topo_sort)
 
302
 
 
303
    def test_topo_sort_1(self):
 
304
        """TopoSort simple nontrivial graph"""
 
305
        self.assertTopoSortOrder({0: [3],
 
306
                                  1: [4],
 
307
                                  2: [1, 4],
 
308
                                  3: [],
 
309
                                  4: [0, 3]})
 
310
 
 
311
    def test_topo_sort_partial(self):
 
312
        """Topological sort with partial ordering.
 
313
 
 
314
        Multiple correct orderings are possible, so test for
 
315
        correctness, not for exact match on the resulting list.
 
316
        """
 
317
        self.assertTopoSortOrder({0: [],
 
318
                                  1: [0],
 
319
                                  2: [0],
 
320
                                  3: [0],
 
321
                                  4: [1, 2, 3],
 
322
                                  5: [1, 2],
 
323
                                  6: [1, 2],
 
324
                                  7: [2, 3],
 
325
                                  8: [0, 1, 4, 5, 6]})
 
326
 
 
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],
 
330
                                  1: [2]})
 
331
 
 
332
 
 
333
class TestKnownGraphMergeSort(TestCaseWithKnownGraph):
 
334
 
 
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)
 
340
                 for n in value]
 
341
        if result_list != value:
 
342
            self.assertEqualDiff(pprint.pformat(result_list),
 
343
                                 pprint.pformat(value))
 
344
 
 
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,), [])
 
350
 
 
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,), [])
 
357
 
 
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': []},
 
362
                                  'id',
 
363
                                  [('id', 0, (1,), True)])
 
364
 
 
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(
 
369
            {'A': [],
 
370
             'B': ['A'],
 
371
             'C': ['B']},
 
372
            'C',
 
373
            [('C', 0, (3,), False),
 
374
             ('B', 0, (2,), False),
 
375
             ('A', 0, (1,), True),
 
376
             ],
 
377
            )
 
378
 
 
379
    def test_sequence_numbers_increase_with_merges(self):
 
380
        # test that sequence numbers increase across merges
 
381
        self.assertSortAndIterate(
 
382
            {'A': [],
 
383
             'B': ['A'],
 
384
             'C': ['A', 'B']},
 
385
            'C',
 
386
            [('C', 0, (2,), False),
 
387
             ('B', 1, (1,1,1), True),
 
388
             ('A', 0, (1,), True),
 
389
             ],
 
390
            )
 
391
 
 
392
    def test_merge_sort_race(self):
 
393
        # A
 
394
        # |
 
395
        # B-.
 
396
        # |\ \
 
397
        # | | C
 
398
        # | |/
 
399
        # | D
 
400
        # |/
 
401
        # F
 
402
        graph = {'A': [],
 
403
                 'B': ['A'],
 
404
                 'C': ['B'],
 
405
                 'D': ['B', 'C'],
 
406
                 'F': ['B', 'D'],
 
407
                 }
 
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),
 
414
             ])
 
415
        # A
 
416
        # |
 
417
        # B-.
 
418
        # |\ \
 
419
        # | X C
 
420
        # | |/
 
421
        # | D
 
422
        # |/
 
423
        # F
 
424
        graph = {'A': [],
 
425
                 'B': ['A'],
 
426
                 'C': ['B'],
 
427
                 'X': ['B'],
 
428
                 'D': ['X', 'C'],
 
429
                 'F': ['B', 'D'],
 
430
                 }
 
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),
 
438
             ])
 
439
 
 
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:
 
444
        #  A 0   [D, B]
 
445
        #  B  1  [C, F]
 
446
        #  C  1  [H]
 
447
        #  D 0   [H, E]
 
448
        #  E  1  [G, F]
 
449
        #  F   2 [G]
 
450
        #  G  1  [H]
 
451
        #  H 0
 
452
        self.assertSortAndIterate(
 
453
            {'A': ['D', 'B'],
 
454
             'B': ['C', 'F'],
 
455
             'C': ['H'],
 
456
             'D': ['H', 'E'],
 
457
             'E': ['G', 'F'],
 
458
             'F': ['G'],
 
459
             'G': ['H'],
 
460
             'H': []
 
461
             },
 
462
            'A',
 
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),
 
471
             ],
 
472
            )
 
473
 
 
474
    def test_dotted_revnos_with_simple_merges(self):
 
475
        # A         1
 
476
        # |\
 
477
        # B C       2, 1.1.1
 
478
        # | |\
 
479
        # D E F     3, 1.1.2, 1.2.1
 
480
        # |/ /|
 
481
        # G H I     4, 1.2.2, 1.3.1
 
482
        # |/ /
 
483
        # J K       5, 1.3.2
 
484
        # |/
 
485
        # L         6
 
486
        self.assertSortAndIterate(
 
487
            {'A': [],
 
488
             'B': ['A'],
 
489
             'C': ['A'],
 
490
             'D': ['B'],
 
491
             'E': ['C'],
 
492
             'F': ['C'],
 
493
             'G': ['D', 'E'],
 
494
             'H': ['F'],
 
495
             'I': ['F'],
 
496
             'J': ['G', 'H'],
 
497
             'K': ['I'],
 
498
             'L': ['J', 'K'],
 
499
            },
 
500
            'L',
 
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),
 
513
             ],
 
514
            )
 
515
        # Adding a shortcut from the first revision should not change any of
 
516
        # the existing numbers
 
517
        self.assertSortAndIterate(
 
518
            {'A': [],
 
519
             'B': ['A'],
 
520
             'C': ['A'],
 
521
             'D': ['B'],
 
522
             'E': ['C'],
 
523
             'F': ['C'],
 
524
             'G': ['D', 'E'],
 
525
             'H': ['F'],
 
526
             'I': ['F'],
 
527
             'J': ['G', 'H'],
 
528
             'K': ['I'],
 
529
             'L': ['J', 'K'],
 
530
             'M': ['A'],
 
531
             'N': ['L', 'M'],
 
532
            },
 
533
            'N',
 
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),
 
548
             ],
 
549
            )
 
550
 
 
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(
 
555
            {'A': ['B'],
 
556
             'B': [],
 
557
             },
 
558
            'A',
 
559
            [('A', 0, (2,), False),
 
560
             ('B', 0, (1,), True)
 
561
             ],
 
562
            )
 
563
 
 
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
 
570
        # A 0    [H, B, E]
 
571
        # B  1   [D, C]
 
572
        # C   2  [D]       *
 
573
        # D  1   [H]       *
 
574
        # E  1   [G, F]
 
575
        # F   2  [G]       *
 
576
        # G  1   [H]       *
 
577
        # H 0    []        *
 
578
        self.assertSortAndIterate(
 
579
            {'A': ['H', 'B', 'E'],
 
580
             'B': ['D', 'C'],
 
581
             'C': ['D'],
 
582
             'D': ['H'],
 
583
             'E': ['G', 'F'],
 
584
             'F': ['G'],
 
585
             'G': ['H'],
 
586
             'H': [],
 
587
             },
 
588
            'A',
 
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),
 
597
             ],
 
598
            )
 
599
 
 
600
    def test_parallel_root_sequence_numbers_increase_with_merges(self):
 
601
        """When there are parallel roots, check their revnos."""
 
602
        self.assertSortAndIterate(
 
603
            {'A': [],
 
604
             'B': [],
 
605
             'C': ['A', 'B']},
 
606
            'C',
 
607
            [('C', 0, (2,), False),
 
608
             ('B', 1, (0,1,1), True),
 
609
             ('A', 0, (1,), True),
 
610
             ],
 
611
            )
 
612
 
 
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']
 
620
        # branch 3:
 
621
        #  I: ['H']
 
622
        #  H: ['A']
 
623
        # merge 2: G: ['D', 'F']
 
624
        # branch 2:
 
625
        #  F: ['E']
 
626
        #  E: ['A']
 
627
        # merge 1: D: ['A', 'C']
 
628
        # branch 1:
 
629
        #  C: ['B']
 
630
        #  B: ['A']
 
631
        # root: A: []
 
632
        self.assertSortAndIterate(
 
633
            {'J': ['G', 'I'],
 
634
             'I': ['H',],
 
635
             'H': ['A'],
 
636
             'G': ['D', 'F'],
 
637
             'F': ['E'],
 
638
             'E': ['A'],
 
639
             'D': ['A', 'C'],
 
640
             'C': ['B'],
 
641
             'B': ['A'],
 
642
             'A': [],
 
643
             },
 
644
            'J',
 
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),
 
655
             ],
 
656
            )
 
657
 
 
658
    def test_roots_and_sub_branches_versus_ghosts(self):
 
659
        """Extra roots and their mini branches use the same numbering.
 
660
 
 
661
        All of them use the 0-node numbering.
 
662
        """
 
663
        #       A D   K
 
664
        #       | |\  |\
 
665
        #       B E F L M
 
666
        #       | |/  |/
 
667
        #       C G   N
 
668
        #       |/    |\
 
669
        #       H I   O P
 
670
        #       |/    |/
 
671
        #       J     Q
 
672
        #       |.---'
 
673
        #       R
 
674
        self.assertSortAndIterate(
 
675
            {'A': [],
 
676
             'B': ['A'],
 
677
             'C': ['B'],
 
678
             'D': [],
 
679
             'E': ['D'],
 
680
             'F': ['D'],
 
681
             'G': ['E', 'F'],
 
682
             'H': ['C', 'G'],
 
683
             'I': [],
 
684
             'J': ['H', 'I'],
 
685
             'K': [],
 
686
             'L': ['K'],
 
687
             'M': ['K'],
 
688
             'N': ['L', 'M'],
 
689
             'O': ['N'],
 
690
             'P': ['N'],
 
691
             'Q': ['O', 'P'],
 
692
             'R': ['J', 'Q'],
 
693
            },
 
694
            'R',
 
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),
 
713
             ],
 
714
            )
 
715
 
 
716
    def test_ghost(self):
 
717
        # merge_sort should be able to ignore ghosts
 
718
        # A
 
719
        # |
 
720
        # B ghost
 
721
        # |/
 
722
        # C
 
723
        self.assertSortAndIterate(
 
724
            {'A': [],
 
725
             'B': ['A'],
 
726
             'C': ['B', 'ghost'],
 
727
            },
 
728
            'C',
 
729
            [('C', 0, (3,), False),
 
730
             ('B', 0, (2,), False),
 
731
             ('A', 0, (1,), True),
 
732
            ])
 
733
 
 
734
    def test_lefthand_ghost(self):
 
735
        # ghost
 
736
        #  |
 
737
        #  A
 
738
        #  |
 
739
        #  B
 
740
        self.assertSortAndIterate(
 
741
            {'A': ['ghost'],
 
742
             'B': ['A'],
 
743
            }, 'B',
 
744
            [('B', 0, (2,), False),
 
745
             ('A', 0, (1,), True),
 
746
            ])
 
747
 
 
748
    def test_graph_cycle(self):
 
749
        # merge_sort should fail with a simple error when a graph cycle is
 
750
        # encountered.
 
751
        #
 
752
        # A
 
753
        # |,-.
 
754
        # B  |
 
755
        # |  |
 
756
        # C  ^
 
757
        # |  |
 
758
        # D  |
 
759
        # |'-'
 
760
        # E
 
761
        self.assertRaises(errors.GraphCycleError,
 
762
            self.assertSortAndIterate,
 
763
                {'A': [],
 
764
                 'B': ['D'],
 
765
                 'C': ['B'],
 
766
                 'D': ['C'],
 
767
                 'E': ['D'],
 
768
                },
 
769
                'E',
 
770
                [])
 
771
 
 
772
 
 
773
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
774
    """Test the sort order returned by gc_sort."""
 
775
 
 
776
    def assertSorted(self, expected, parent_map):
 
777
        graph = self.make_known_graph(parent_map)
 
778
        value = graph.gc_sort()
 
779
        if expected != value:
 
780
            self.assertEqualDiff(pprint.pformat(expected),
 
781
                                 pprint.pformat(value))
 
782
 
 
783
    def test_empty(self):
 
784
        self.assertSorted([], {})
 
785
 
 
786
    def test_single(self):
 
787
        self.assertSorted(['a'], {'a':()})
 
788
        self.assertSorted([('a',)], {('a',):()})
 
789
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
790
 
 
791
    def test_linear(self):
 
792
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
793
        self.assertSorted([('c',), ('b',), ('a',)],
 
794
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
795
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
796
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
797
                           ('F', 'c'): (('F', 'b'),)})
 
798
 
 
799
    def test_mixed_ancestries(self):
 
800
        # Each prefix should be sorted separately
 
801
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
802
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
803
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
804
                          ],
 
805
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
806
                           ('F', 'c'): (('F', 'b'),),
 
807
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
808
                           ('G', 'c'): (('G', 'b'),),
 
809
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
810
                           ('Q', 'c'): (('Q', 'b'),),
 
811
                          })
 
812
 
 
813
    def test_stable_sorting(self):
 
814
        # the sort order should be stable even when extra nodes are added
 
815
        self.assertSorted(['b', 'c', 'a'],
 
816
                          {'a':(), 'b':('a',), 'c':('a',)})
 
817
        self.assertSorted(['b', 'c', 'd', 'a'],
 
818
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
819
        self.assertSorted(['b', 'c', 'd', 'a'],
 
820
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
821
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
822
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
823
                           'Z':('a',)})
 
824
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
825
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
826
                           'Z':('a',),
 
827
                           'e':('b', 'c', 'd'),
 
828
                           'f':('d', 'Z'),
 
829
                           })
 
830
 
 
831
    def test_skip_ghost(self):
 
832
        self.assertSorted(['b', 'c', 'a'],
 
833
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
834
 
 
835
    def test_skip_mainline_ghost(self):
 
836
        self.assertSorted(['b', 'c', 'a'],
 
837
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})