/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: John Arbash Meinel
  • Date: 2009-10-12 18:10:24 UTC
  • mto: This revision was merged to the branch mainline in revision 4736.
  • Revision ID: john@arbash-meinel.com-20091012181024-q21zm9xpyf62ld7t
Add some tests that we *can* compare to strings, even if we don't care
what the result actually is.

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