← 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: Jelmer Vernooij
  • Date: 2010-12-20 11:57:14 UTC
  • mto: This revision was merged to the branch mainline in revision 5577.
  • Revision ID: jelmer@samba.org-20101220115714-2ru3hfappjweeg7q
Don't use no-plugins.

Show diffs side-by-side

added added

removed removed

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