← 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: Vincent Ladeuil
  • Date: 2009-12-14 15:51:36 UTC
  • mto: (4894.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4895.
  • Revision ID: v.ladeuil+lp@free.fr-20091214155136-rf4nkqvxda9oiw4u
Cleanup tests and tweak the text displayed.

* bzrlib/tests/blackbox/test_update.py:
Fix imports and replace the assertContainsRe with assertEqualDiff
to make the test clearer, more robust and easier to debug.

* bzrlib/tests/commands/test_update.py: 
Fix imports.

* bzrlib/tests/blackbox/test_filtered_view_ops.py: 
Fix imports and strange accesses to base class methods.
(TestViewTreeOperations.test_view_on_update): Avoid os.chdir()
call, simplify string matching assertions.

* bzrlib/builtins.py:
(cmd_update.run): Fix spurious space, get rid of the final '/' for
the base path, don't add a final period (it's a legal char in a
path and would be annoying for people that like to copy/paste).

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