/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: Aaron Bentley
  • Date: 2007-12-08 01:00:58 UTC
  • mfrom: (3095 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3133.
  • Revision ID: aaron.bentley@utoronto.ca-20071208010058-1vuj9qn49qfu808e
Merge bzr.dev

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 TestGraph(TestCaseWithMemoryTransport):
 
149
 
 
150
    def make_graph(self, ancestors):
 
151
        tree = self.prepare_memory_tree('.')
 
152
        self.build_ancestry(tree, ancestors)
 
153
        self.addCleanup(tree.unlock)
 
154
        return tree.branch.repository.get_graph()
 
155
 
 
156
    def prepare_memory_tree(self, location):
 
157
        tree = self.make_branch_and_memory_tree(location)
 
158
        tree.lock_write()
 
159
        tree.add('.')
 
160
        return tree
 
161
 
 
162
    def build_ancestry(self, tree, ancestors):
 
163
        """Create an ancestry as specified by a graph dict
 
164
 
 
165
        :param tree: A tree to use
 
166
        :param ancestors: a dict of {node: [node_parent, ...]}
 
167
        """
 
168
        pending = [NULL_REVISION]
 
169
        descendants = {}
 
170
        for descendant, parents in ancestors.iteritems():
 
171
            for parent in parents:
 
172
                descendants.setdefault(parent, []).append(descendant)
 
173
        while len(pending) > 0:
 
174
            cur_node = pending.pop()
 
175
            for descendant in descendants.get(cur_node, []):
 
176
                if tree.branch.repository.has_revision(descendant):
 
177
                    continue
 
178
                parents = [p for p in ancestors[descendant] if p is not
 
179
                           NULL_REVISION]
 
180
                if len([p for p in parents if not
 
181
                    tree.branch.repository.has_revision(p)]) > 0:
 
182
                    continue
 
183
                tree.set_parent_ids(parents)
 
184
                if len(parents) > 0:
 
185
                    left_parent = parents[0]
 
186
                else:
 
187
                    left_parent = NULL_REVISION
 
188
                tree.branch.set_last_revision_info(
 
189
                    len(tree.branch._lefthand_history(left_parent)),
 
190
                    left_parent)
 
191
                tree.commit(descendant, rev_id=descendant)
 
192
                pending.append(descendant)
 
193
 
 
194
    def test_lca(self):
 
195
        """Test finding least common ancestor.
 
196
 
 
197
        ancestry_1 should always have a single common ancestor
 
198
        """
 
199
        graph = self.make_graph(ancestry_1)
 
200
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
 
201
        self.assertEqual(set([NULL_REVISION]),
 
202
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
 
203
        self.assertEqual(set([NULL_REVISION]),
 
204
                         graph.find_lca(NULL_REVISION, 'rev1'))
 
205
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
 
206
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
207
 
 
208
    def test_no_unique_lca(self):
 
209
        """Test error when one revision is not in the graph"""
 
210
        graph = self.make_graph(ancestry_1)
 
211
        self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
 
212
                          'rev1', '1rev')
 
213
 
 
214
    def test_lca_criss_cross(self):
 
215
        """Test least-common-ancestor after a criss-cross merge."""
 
216
        graph = self.make_graph(criss_cross)
 
217
        self.assertEqual(set(['rev2a', 'rev2b']),
 
218
                         graph.find_lca('rev3a', 'rev3b'))
 
219
        self.assertEqual(set(['rev2b']),
 
220
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
 
221
 
 
222
    def test_lca_shortcut(self):
 
223
        """Test least-common ancestor on this history shortcut"""
 
224
        graph = self.make_graph(history_shortcut)
 
225
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
226
 
 
227
    def test_recursive_unique_lca(self):
 
228
        """Test finding a unique least common ancestor.
 
229
 
 
230
        ancestry_1 should always have a single common ancestor
 
231
        """
 
232
        graph = self.make_graph(ancestry_1)
 
233
        self.assertEqual(NULL_REVISION,
 
234
                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
 
235
        self.assertEqual(NULL_REVISION,
 
236
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
 
237
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
 
238
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
 
239
        self.assertEqual(('rev1', 1,),
 
240
                         graph.find_unique_lca('rev2a', 'rev2b',
 
241
                         count_steps=True))
 
242
 
 
243
    def test_unique_lca_criss_cross(self):
 
244
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
245
        graph = self.make_graph(criss_cross)
 
246
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
247
        lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
 
248
        self.assertEqual('rev1', lca)
 
249
        self.assertEqual(2, steps)
 
250
 
 
251
    def test_unique_lca_null_revision(self):
 
252
        """Ensure we pick NULL_REVISION when necessary"""
 
253
        graph = self.make_graph(criss_cross2)
 
254
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
255
        self.assertEqual(NULL_REVISION,
 
256
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
257
 
 
258
    def test_unique_lca_null_revision2(self):
 
259
        """Ensure we pick NULL_REVISION when necessary"""
 
260
        graph = self.make_graph(ancestry_2)
 
261
        self.assertEqual(NULL_REVISION,
 
262
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
263
 
 
264
    def test_common_ancestor_two_repos(self):
 
265
        """Ensure we do unique_lca using data from two repos"""
 
266
        mainline_tree = self.prepare_memory_tree('mainline')
 
267
        self.build_ancestry(mainline_tree, mainline)
 
268
        self.addCleanup(mainline_tree.unlock)
 
269
 
 
270
        # This is cheating, because the revisions in the graph are actually
 
271
        # different revisions, despite having the same revision-id.
 
272
        feature_tree = self.prepare_memory_tree('feature')
 
273
        self.build_ancestry(feature_tree, feature_branch)
 
274
        self.addCleanup(feature_tree.unlock)
 
275
 
 
276
        graph = mainline_tree.branch.repository.get_graph(
 
277
            feature_tree.branch.repository)
 
278
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
279
 
 
280
    def test_graph_difference(self):
 
281
        graph = self.make_graph(ancestry_1)
 
282
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
283
        self.assertEqual((set(), set(['rev1'])),
 
284
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
285
        self.assertEqual((set(['rev1']), set()),
 
286
                         graph.find_difference('rev1', NULL_REVISION))
 
287
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
288
                         graph.find_difference('rev3', 'rev2b'))
 
289
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
290
                         graph.find_difference('rev4', 'rev2b'))
 
291
 
 
292
    def test_graph_difference_criss_cross(self):
 
293
        graph = self.make_graph(criss_cross)
 
294
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
295
                         graph.find_difference('rev3a', 'rev3b'))
 
296
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
297
                         graph.find_difference('rev2a', 'rev3b'))
 
298
 
 
299
    def test_stacked_parents_provider(self):
 
300
 
 
301
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
302
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
303
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
304
        self.assertEqual([['rev4',], ['rev3']],
 
305
                         stacked.get_parents(['rev1', 'rev2']))
 
306
        self.assertEqual([['rev3',], ['rev4']],
 
307
                         stacked.get_parents(['rev2', 'rev1']))
 
308
        self.assertEqual([['rev3',], ['rev3']],
 
309
                         stacked.get_parents(['rev2', 'rev2']))
 
310
        self.assertEqual([['rev4',], ['rev4']],
 
311
                         stacked.get_parents(['rev1', 'rev1']))
 
312
 
 
313
    def test_iter_topo_order(self):
 
314
        graph = self.make_graph(ancestry_1)
 
315
        args = ['rev2a', 'rev3', 'rev1']
 
316
        topo_args = list(graph.iter_topo_order(args))
 
317
        self.assertEqual(set(args), set(topo_args))
 
318
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
 
319
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
320
 
 
321
    def test_is_ancestor(self):
 
322
        graph = self.make_graph(ancestry_1)
 
323
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
324
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
325
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
326
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
327
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
328
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
329
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
330
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
331
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
332
        instrumented_provider = InstrumentedParentsProvider(graph)
 
333
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
334
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
335
        self.assertTrue('null:' not in instrumented_provider.calls)
 
336
 
 
337
    def test_is_ancestor_boundary(self):
 
338
        """Ensure that we avoid searching the whole graph.
 
339
        
 
340
        This requires searching through b as a common ancestor, so we
 
341
        can identify that e is common.
 
342
        """
 
343
        graph = self.make_graph(boundary)
 
344
        instrumented_provider = InstrumentedParentsProvider(graph)
 
345
        graph = _mod_graph.Graph(instrumented_provider)
 
346
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
347
        self.assertTrue('null:' not in instrumented_provider.calls)
 
348
 
 
349
    def test_filter_candidate_lca(self):
 
350
        """Test filter_candidate_lca for a corner case
 
351
 
 
352
        This tests the case where we encounter the end of iteration for 'e'
 
353
        in the same pass as we discover that 'd' is an ancestor of 'e', and
 
354
        therefore 'e' can't be an lca.
 
355
 
 
356
        To compensate for different dict orderings on other Python
 
357
        implementations, we mirror 'd' and 'e' with 'b' and 'a'.
 
358
        """
 
359
        # This test is sensitive to the iteration order of dicts.  It will
 
360
        # pass incorrectly if 'e' and 'a' sort before 'c'
 
361
        #
 
362
        # NULL_REVISION
 
363
        #     / \
 
364
        #    a   e
 
365
        #    |   |
 
366
        #    b   d
 
367
        #     \ /
 
368
        #      c
 
369
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
 
370
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
 
371
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
 
372
 
 
373
    def test_heads_null(self):
 
374
        graph = self.make_graph(ancestry_1)
 
375
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
376
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
377
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
378
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
379
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
380
 
 
381
    def test_heads_one(self):
 
382
        # A single node will always be a head
 
383
        graph = self.make_graph(ancestry_1)
 
384
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
385
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
386
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
387
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
388
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
389
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
390
 
 
391
    def test_heads_single(self):
 
392
        graph = self.make_graph(ancestry_1)
 
393
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
394
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
395
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
396
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
397
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
398
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
399
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
400
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
401
 
 
402
    def test_heads_two_heads(self):
 
403
        graph = self.make_graph(ancestry_1)
 
404
        self.assertEqual(set(['rev2a', 'rev2b']),
 
405
                         graph.heads(['rev2a', 'rev2b']))
 
406
        self.assertEqual(set(['rev3', 'rev2b']),
 
407
                         graph.heads(['rev3', 'rev2b']))
 
408
 
 
409
    def test_heads_criss_cross(self):
 
410
        graph = self.make_graph(criss_cross)
 
411
        self.assertEqual(set(['rev2a']),
 
412
                         graph.heads(['rev2a', 'rev1']))
 
413
        self.assertEqual(set(['rev2b']),
 
414
                         graph.heads(['rev2b', 'rev1']))
 
415
        self.assertEqual(set(['rev3a']),
 
416
                         graph.heads(['rev3a', 'rev1']))
 
417
        self.assertEqual(set(['rev3b']),
 
418
                         graph.heads(['rev3b', 'rev1']))
 
419
        self.assertEqual(set(['rev2a', 'rev2b']),
 
420
                         graph.heads(['rev2a', 'rev2b']))
 
421
        self.assertEqual(set(['rev3a']),
 
422
                         graph.heads(['rev3a', 'rev2a']))
 
423
        self.assertEqual(set(['rev3a']),
 
424
                         graph.heads(['rev3a', 'rev2b']))
 
425
        self.assertEqual(set(['rev3a']),
 
426
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
427
        self.assertEqual(set(['rev3b']),
 
428
                         graph.heads(['rev3b', 'rev2a']))
 
429
        self.assertEqual(set(['rev3b']),
 
430
                         graph.heads(['rev3b', 'rev2b']))
 
431
        self.assertEqual(set(['rev3b']),
 
432
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
433
        self.assertEqual(set(['rev3a', 'rev3b']),
 
434
                         graph.heads(['rev3a', 'rev3b']))
 
435
        self.assertEqual(set(['rev3a', 'rev3b']),
 
436
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
437
 
 
438
    def test_heads_shortcut(self):
 
439
        graph = self.make_graph(history_shortcut)
 
440
 
 
441
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
442
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
443
        self.assertEqual(set(['rev3a', 'rev3b']),
 
444
                         graph.heads(['rev3a', 'rev3b']))
 
445
        self.assertEqual(set(['rev3a', 'rev3b']),
 
446
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
447
        self.assertEqual(set(['rev2a', 'rev3b']),
 
448
                         graph.heads(['rev2a', 'rev3b']))
 
449
        self.assertEqual(set(['rev2c', 'rev3a']),
 
450
                         graph.heads(['rev2c', 'rev3a']))
 
451
 
 
452
    def _run_heads_break_deeper(self, graph_dict, search):
 
453
        """Run heads on a graph-as-a-dict.
 
454
        
 
455
        If the search asks for the parents of 'deeper' the test will fail.
 
456
        """
 
457
        class stub(object):
 
458
            pass
 
459
        def get_parents(keys):
 
460
            result = []
 
461
            for key in keys:
 
462
                if key == 'deeper':
 
463
                    self.fail('key deeper was accessed')
 
464
                result.append(graph_dict[key])
 
465
            return result
 
466
        an_obj = stub()
 
467
        an_obj.get_parents = get_parents
 
468
        graph = _mod_graph.Graph(an_obj)
 
469
        return graph.heads(search)
 
470
 
 
471
    def test_heads_limits_search(self):
 
472
        # test that a heads query does not search all of history
 
473
        graph_dict = {
 
474
            'left':['common'],
 
475
            'right':['common'],
 
476
            'common':['deeper'],
 
477
        }
 
478
        self.assertEqual(set(['left', 'right']),
 
479
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
480
 
 
481
    def test_heads_limits_search_assymetric(self):
 
482
        # test that a heads query does not search all of history
 
483
        graph_dict = {
 
484
            'left':['midleft'],
 
485
            'midleft':['common'],
 
486
            'right':['common'],
 
487
            'common':['aftercommon'],
 
488
            'aftercommon':['deeper'],
 
489
        }
 
490
        self.assertEqual(set(['left', 'right']),
 
491
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
492
 
 
493
    def test_heads_limits_search_common_search_must_continue(self):
 
494
        # test that common nodes are still queried, preventing
 
495
        # all-the-way-to-origin behaviour in the following graph:
 
496
        graph_dict = {
 
497
            'h1':['shortcut', 'common1'],
 
498
            'h2':['common1'],
 
499
            'shortcut':['common2'],
 
500
            'common1':['common2'],
 
501
            'common2':['deeper'],
 
502
        }
 
503
        self.assertEqual(set(['h1', 'h2']),
 
504
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))