/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Robert Collins
  • Date: 2007-11-22 00:05:12 UTC
  • mto: This revision was merged to the branch mainline in revision 3014.
  • Revision ID: robertc@robertcollins.net-20071122000512-27cvsv9vs6k0s4hn
test_merge_directive locking correctness.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
 
1
# Copyright (C) 2007 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
from bzrlib import (
 
18
    errors,
 
19
    graph as _mod_graph,
 
20
    )
 
21
from bzrlib.revision import NULL_REVISION
 
22
from bzrlib.tests import TestCaseWithMemoryTransport
 
23
 
 
24
 
 
25
# Ancestry 1:
 
26
#
 
27
#  NULL_REVISION
 
28
#       |
 
29
#     rev1
 
30
#      /\
 
31
#  rev2a rev2b
 
32
#     |    |
 
33
#   rev3  /
 
34
#     |  /
 
35
#   rev4
 
36
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
37
              'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
 
38
 
 
39
 
 
40
# Ancestry 2:
 
41
#
 
42
#  NULL_REVISION
 
43
#    /    \
 
44
# rev1a  rev1b
 
45
#   |
 
46
# rev2a
 
47
#   |
 
48
# rev3a
 
49
#   |
 
50
# rev4a
 
51
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
 
52
              'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
 
53
 
 
54
 
 
55
# Criss cross ancestry
 
56
#
 
57
#     NULL_REVISION
 
58
#         |
 
59
#        rev1
 
60
#        /  \
 
61
#    rev2a  rev2b
 
62
#       |\  /|
 
63
#       |  X |
 
64
#       |/  \|
 
65
#    rev3a  rev3b
 
66
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
67
               'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
 
68
 
 
69
 
 
70
# Criss-cross 2
 
71
#
 
72
#  NULL_REVISION
 
73
#    /   \
 
74
# rev1a  rev1b
 
75
#   |\   /|
 
76
#   | \ / |
 
77
#   |  X  |
 
78
#   | / \ |
 
79
#   |/   \|
 
80
# rev2a  rev2b
 
81
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
 
82
                'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
 
83
 
 
84
 
 
85
# Mainline:
 
86
#
 
87
#  NULL_REVISION
 
88
#       |
 
89
#      rev1
 
90
#      /  \
 
91
#      | rev2b
 
92
#      |  /
 
93
#     rev2a
 
94
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
 
95
            'rev2b': ['rev1']}
 
96
 
 
97
 
 
98
# feature branch:
 
99
#
 
100
#  NULL_REVISION
 
101
#       |
 
102
#      rev1
 
103
#       |
 
104
#     rev2b
 
105
#       |
 
106
#     rev3b
 
107
feature_branch = {'rev1': [NULL_REVISION],
 
108
                  'rev2b': ['rev1'], 'rev3b': ['rev2b']}
 
109
 
 
110
 
 
111
# History shortcut
 
112
#  NULL_REVISION
 
113
#       |
 
114
#     rev1------
 
115
#     /  \      \
 
116
#  rev2a rev2b rev2c
 
117
#    |  /   \   /
 
118
#  rev3a    reveb
 
119
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
 
120
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
 
121
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
 
122
 
 
123
#  NULL_REVISION
 
124
#       |
 
125
#       f
 
126
#       |
 
127
#       e
 
128
#      / \
 
129
#     b   d
 
130
#     | \ |
 
131
#     a   c
 
132
 
 
133
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
 
134
            'f':[NULL_REVISION]}
 
135
 
 
136
 
 
137
class InstrumentedParentsProvider(object):
 
138
 
 
139
    def __init__(self, parents_provider):
 
140
        self.calls = []
 
141
        self._real_parents_provider = parents_provider
 
142
 
 
143
    def get_parents(self, nodes):
 
144
        self.calls.extend(nodes)
 
145
        return self._real_parents_provider.get_parents(nodes)
 
146
 
 
147
 
 
148
class DictParentsProvider(object):
 
149
 
 
150
    def __init__(self, ancestry):
 
151
        self.ancestry = ancestry
 
152
 
 
153
    def __repr__(self):
 
154
        return 'DictParentsProvider(%r)' % self.ancestry
 
155
 
 
156
    def get_parents(self, revisions):
 
157
        return [self.ancestry.get(r, None) for r in revisions]
 
158
 
 
159
 
 
160
class TestGraph(TestCaseWithMemoryTransport):
 
161
 
 
162
    def make_graph(self, ancestors):
 
163
        tree = self.prepare_memory_tree('.')
 
164
        self.build_ancestry(tree, ancestors)
 
165
        self.addCleanup(tree.unlock)
 
166
        return tree.branch.repository.get_graph()
 
167
 
 
168
    def prepare_memory_tree(self, location):
 
169
        tree = self.make_branch_and_memory_tree(location)
 
170
        tree.lock_write()
 
171
        tree.add('.')
 
172
        return tree
 
173
 
 
174
    def build_ancestry(self, tree, ancestors):
 
175
        """Create an ancestry as specified by a graph dict
 
176
 
 
177
        :param tree: A tree to use
 
178
        :param ancestors: a dict of {node: [node_parent, ...]}
 
179
        """
 
180
        pending = [NULL_REVISION]
 
181
        descendants = {}
 
182
        for descendant, parents in ancestors.iteritems():
 
183
            for parent in parents:
 
184
                descendants.setdefault(parent, []).append(descendant)
 
185
        while len(pending) > 0:
 
186
            cur_node = pending.pop()
 
187
            for descendant in descendants.get(cur_node, []):
 
188
                if tree.branch.repository.has_revision(descendant):
 
189
                    continue
 
190
                parents = [p for p in ancestors[descendant] if p is not
 
191
                           NULL_REVISION]
 
192
                if len([p for p in parents if not
 
193
                    tree.branch.repository.has_revision(p)]) > 0:
 
194
                    continue
 
195
                tree.set_parent_ids(parents)
 
196
                if len(parents) > 0:
 
197
                    left_parent = parents[0]
 
198
                else:
 
199
                    left_parent = NULL_REVISION
 
200
                tree.branch.set_last_revision_info(
 
201
                    len(tree.branch._lefthand_history(left_parent)),
 
202
                    left_parent)
 
203
                tree.commit(descendant, rev_id=descendant)
 
204
                pending.append(descendant)
 
205
 
 
206
    def test_lca(self):
 
207
        """Test finding least common ancestor.
 
208
 
 
209
        ancestry_1 should always have a single common ancestor
 
210
        """
 
211
        graph = self.make_graph(ancestry_1)
 
212
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
 
213
        self.assertEqual(set([NULL_REVISION]),
 
214
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
 
215
        self.assertEqual(set([NULL_REVISION]),
 
216
                         graph.find_lca(NULL_REVISION, 'rev1'))
 
217
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
 
218
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
219
 
 
220
    def test_no_unique_lca(self):
 
221
        """Test error when one revision is not in the graph"""
 
222
        graph = self.make_graph(ancestry_1)
 
223
        self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
 
224
                          'rev1', '1rev')
 
225
 
 
226
    def test_lca_criss_cross(self):
 
227
        """Test least-common-ancestor after a criss-cross merge."""
 
228
        graph = self.make_graph(criss_cross)
 
229
        self.assertEqual(set(['rev2a', 'rev2b']),
 
230
                         graph.find_lca('rev3a', 'rev3b'))
 
231
        self.assertEqual(set(['rev2b']),
 
232
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
 
233
 
 
234
    def test_lca_shortcut(self):
 
235
        """Test least-common ancestor on this history shortcut"""
 
236
        graph = self.make_graph(history_shortcut)
 
237
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
238
 
 
239
    def test_recursive_unique_lca(self):
 
240
        """Test finding a unique least common ancestor.
 
241
 
 
242
        ancestry_1 should always have a single common ancestor
 
243
        """
 
244
        graph = self.make_graph(ancestry_1)
 
245
        self.assertEqual(NULL_REVISION,
 
246
                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
 
247
        self.assertEqual(NULL_REVISION,
 
248
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
 
249
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
 
250
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
 
251
 
 
252
    def test_unique_lca_criss_cross(self):
 
253
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
254
        graph = self.make_graph(criss_cross)
 
255
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
256
 
 
257
    def test_unique_lca_null_revision(self):
 
258
        """Ensure we pick NULL_REVISION when necessary"""
 
259
        graph = self.make_graph(criss_cross2)
 
260
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
261
        self.assertEqual(NULL_REVISION,
 
262
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
263
 
 
264
    def test_unique_lca_null_revision2(self):
 
265
        """Ensure we pick NULL_REVISION when necessary"""
 
266
        graph = self.make_graph(ancestry_2)
 
267
        self.assertEqual(NULL_REVISION,
 
268
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
269
 
 
270
    def test_common_ancestor_two_repos(self):
 
271
        """Ensure we do unique_lca using data from two repos"""
 
272
        mainline_tree = self.prepare_memory_tree('mainline')
 
273
        self.build_ancestry(mainline_tree, mainline)
 
274
        self.addCleanup(mainline_tree.unlock)
 
275
 
 
276
        # This is cheating, because the revisions in the graph are actually
 
277
        # different revisions, despite having the same revision-id.
 
278
        feature_tree = self.prepare_memory_tree('feature')
 
279
        self.build_ancestry(feature_tree, feature_branch)
 
280
        self.addCleanup(feature_tree.unlock)
 
281
 
 
282
        graph = mainline_tree.branch.repository.get_graph(
 
283
            feature_tree.branch.repository)
 
284
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
285
 
 
286
    def test_graph_difference(self):
 
287
        graph = self.make_graph(ancestry_1)
 
288
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
289
        self.assertEqual((set(), set(['rev1'])),
 
290
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
291
        self.assertEqual((set(['rev1']), set()),
 
292
                         graph.find_difference('rev1', NULL_REVISION))
 
293
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
294
                         graph.find_difference('rev3', 'rev2b'))
 
295
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
296
                         graph.find_difference('rev4', 'rev2b'))
 
297
 
 
298
    def test_graph_difference_criss_cross(self):
 
299
        graph = self.make_graph(criss_cross)
 
300
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
301
                         graph.find_difference('rev3a', 'rev3b'))
 
302
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
303
                         graph.find_difference('rev2a', 'rev3b'))
 
304
 
 
305
    def test_stacked_parents_provider(self):
 
306
 
 
307
        parents1 = DictParentsProvider({'rev2': ['rev3']})
 
308
        parents2 = DictParentsProvider({'rev1': ['rev4']})
 
309
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
310
        self.assertEqual([['rev4',], ['rev3']],
 
311
                         stacked.get_parents(['rev1', 'rev2']))
 
312
        self.assertEqual([['rev3',], ['rev4']],
 
313
                         stacked.get_parents(['rev2', 'rev1']))
 
314
        self.assertEqual([['rev3',], ['rev3']],
 
315
                         stacked.get_parents(['rev2', 'rev2']))
 
316
        self.assertEqual([['rev4',], ['rev4']],
 
317
                         stacked.get_parents(['rev1', 'rev1']))
 
318
 
 
319
    def test_iter_topo_order(self):
 
320
        graph = self.make_graph(ancestry_1)
 
321
        args = ['rev2a', 'rev3', 'rev1']
 
322
        topo_args = list(graph.iter_topo_order(args))
 
323
        self.assertEqual(set(args), set(topo_args))
 
324
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
 
325
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
326
 
 
327
    def test_is_ancestor(self):
 
328
        graph = self.make_graph(ancestry_1)
 
329
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
330
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
331
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
332
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
333
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
334
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
335
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
336
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
337
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
338
        instrumented_provider = InstrumentedParentsProvider(graph)
 
339
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
340
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
341
        self.assertTrue('null:' not in instrumented_provider.calls)
 
342
 
 
343
    def test_is_ancestor_boundary(self):
 
344
        """Ensure that we avoid searching the whole graph.
 
345
        
 
346
        This requires searching through b as a common ancestor, so we
 
347
        can identify that e is common.
 
348
        """
 
349
        graph = self.make_graph(boundary)
 
350
        instrumented_provider = InstrumentedParentsProvider(graph)
 
351
        graph = _mod_graph.Graph(instrumented_provider)
 
352
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
353
        self.assertTrue('null:' not in instrumented_provider.calls)
 
354
 
 
355
    def test_filter_candidate_lca(self):
 
356
        """Test filter_candidate_lca for a corner case
 
357
 
 
358
        This tests the case where we encounter the end of iteration for 'e'
 
359
        in the same pass as we discover that 'd' is an ancestor of 'e', and
 
360
        therefore 'e' can't be an lca.
 
361
 
 
362
        To compensate for different dict orderings on other Python
 
363
        implementations, we mirror 'd' and 'e' with 'b' and 'a'.
 
364
        """
 
365
        # This test is sensitive to the iteration order of dicts.  It will
 
366
        # pass incorrectly if 'e' and 'a' sort before 'c'
 
367
        #
 
368
        # NULL_REVISION
 
369
        #     / \
 
370
        #    a   e
 
371
        #    |   |
 
372
        #    b   d
 
373
        #     \ /
 
374
        #      c
 
375
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
 
376
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
 
377
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
 
378
 
 
379
    def test_heads_null(self):
 
380
        graph = self.make_graph(ancestry_1)
 
381
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
382
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
383
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
384
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
385
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
386
 
 
387
    def test_heads_one(self):
 
388
        # A single node will alwaya be a head
 
389
        graph = self.make_graph(ancestry_1)
 
390
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
391
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
392
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
393
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
394
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
395
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
396
 
 
397
    def test_heads_single(self):
 
398
        graph = self.make_graph(ancestry_1)
 
399
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
400
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
401
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
402
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
403
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
404
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
405
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
406
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
407
 
 
408
    def test_heads_two_heads(self):
 
409
        graph = self.make_graph(ancestry_1)
 
410
        self.assertEqual(set(['rev2a', 'rev2b']),
 
411
                         graph.heads(['rev2a', 'rev2b']))
 
412
        self.assertEqual(set(['rev3', 'rev2b']),
 
413
                         graph.heads(['rev3', 'rev2b']))
 
414
 
 
415
    def test_heads_criss_cross(self):
 
416
        graph = self.make_graph(criss_cross)
 
417
        self.assertEqual(set(['rev2a']),
 
418
                         graph.heads(['rev2a', 'rev1']))
 
419
        self.assertEqual(set(['rev2b']),
 
420
                         graph.heads(['rev2b', 'rev1']))
 
421
        self.assertEqual(set(['rev3a']),
 
422
                         graph.heads(['rev3a', 'rev1']))
 
423
        self.assertEqual(set(['rev3b']),
 
424
                         graph.heads(['rev3b', 'rev1']))
 
425
        self.assertEqual(set(['rev2a', 'rev2b']),
 
426
                         graph.heads(['rev2a', 'rev2b']))
 
427
        self.assertEqual(set(['rev3a']),
 
428
                         graph.heads(['rev3a', 'rev2a']))
 
429
        self.assertEqual(set(['rev3a']),
 
430
                         graph.heads(['rev3a', 'rev2b']))
 
431
        self.assertEqual(set(['rev3a']),
 
432
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
433
        self.assertEqual(set(['rev3b']),
 
434
                         graph.heads(['rev3b', 'rev2a']))
 
435
        self.assertEqual(set(['rev3b']),
 
436
                         graph.heads(['rev3b', 'rev2b']))
 
437
        self.assertEqual(set(['rev3b']),
 
438
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
439
        self.assertEqual(set(['rev3a', 'rev3b']),
 
440
                         graph.heads(['rev3a', 'rev3b']))
 
441
        self.assertEqual(set(['rev3a', 'rev3b']),
 
442
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
443
 
 
444
    def test_heads_shortcut(self):
 
445
        graph = self.make_graph(history_shortcut)
 
446
 
 
447
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
448
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
449
        self.assertEqual(set(['rev3a', 'rev3b']),
 
450
                         graph.heads(['rev3a', 'rev3b']))
 
451
        self.assertEqual(set(['rev3a', 'rev3b']),
 
452
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
453
        self.assertEqual(set(['rev2a', 'rev3b']),
 
454
                         graph.heads(['rev2a', 'rev3b']))
 
455
        self.assertEqual(set(['rev2c', 'rev3a']),
 
456
                         graph.heads(['rev2c', 'rev3a']))
 
457
 
 
458
    def _run_heads_break_deeper(self, graph_dict, search):
 
459
        """Run heads on a graph-as-a-dict.
 
460
        
 
461
        If the search asks for the parents of 'deeper' the test will fail.
 
462
        """
 
463
        class stub(object):
 
464
            pass
 
465
        def get_parents(keys):
 
466
            result = []
 
467
            for key in keys:
 
468
                if key == 'deeper':
 
469
                    self.fail('key deeper was accessed')
 
470
                result.append(graph_dict[key])
 
471
            return result
 
472
        an_obj = stub()
 
473
        an_obj.get_parents = get_parents
 
474
        graph = _mod_graph.Graph(an_obj)
 
475
        return graph.heads(search)
 
476
 
 
477
    def test_heads_limits_search(self):
 
478
        # test that a heads query does not search all of history
 
479
        graph_dict = {
 
480
            'left':['common'],
 
481
            'right':['common'],
 
482
            'common':['deeper'],
 
483
        }
 
484
        self.assertEqual(set(['left', 'right']),
 
485
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
486
 
 
487
    def test_heads_limits_search_assymetric(self):
 
488
        # test that a heads query does not search all of history
 
489
        graph_dict = {
 
490
            'left':['midleft'],
 
491
            'midleft':['common'],
 
492
            'right':['common'],
 
493
            'common':['aftercommon'],
 
494
            'aftercommon':['deeper'],
 
495
        }
 
496
        self.assertEqual(set(['left', 'right']),
 
497
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
498
 
 
499
    def test_heads_limits_search_common_search_must_continue(self):
 
500
        # test that common nodes are still queried, preventing
 
501
        # all-the-way-to-origin behaviour in the following graph:
 
502
        graph_dict = {
 
503
            'h1':['shortcut', 'common1'],
 
504
            'h2':['common1'],
 
505
            'shortcut':['common2'],
 
506
            'common1':['common2'],
 
507
            'common2':['deeper'],
 
508
        }
 
509
        self.assertEqual(set(['h1', 'h2']),
 
510
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))