← 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: Martin Pool
  • Date: 2011-07-04 21:15:24 UTC
  • mto: (6034.1.1 filter-tree)
  • mto: This revision was merged to the branch mainline in revision 6035.
  • Revision ID: mbp@canonical.com-20110704211524-ilb7l6g4i3iizke7
Test exporting filtered tree to a zip (already works)

Show diffs side-by-side

added added

removed removed

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