← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Aaron Bentley
  • Date: 2007-12-12 15:17:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3113.
  • Revision ID: abentley@panoramicfeedback.com-20071212151713-ox5n8rlx8m3nsspy
Add support for reconfiguring repositories into branches or trees

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
 
 
240
    def test_unique_lca_criss_cross(self):
 
241
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
242
        graph = self.make_graph(criss_cross)
 
243
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
244
 
 
245
    def test_unique_lca_null_revision(self):
 
246
        """Ensure we pick NULL_REVISION when necessary"""
 
247
        graph = self.make_graph(criss_cross2)
 
248
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
249
        self.assertEqual(NULL_REVISION,
 
250
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
251
 
 
252
    def test_unique_lca_null_revision2(self):
 
253
        """Ensure we pick NULL_REVISION when necessary"""
 
254
        graph = self.make_graph(ancestry_2)
 
255
        self.assertEqual(NULL_REVISION,
 
256
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
257
 
 
258
    def test_common_ancestor_two_repos(self):
 
259
        """Ensure we do unique_lca using data from two repos"""
 
260
        mainline_tree = self.prepare_memory_tree('mainline')
 
261
        self.build_ancestry(mainline_tree, mainline)
 
262
        self.addCleanup(mainline_tree.unlock)
 
263
 
 
264
        # This is cheating, because the revisions in the graph are actually
 
265
        # different revisions, despite having the same revision-id.
 
266
        feature_tree = self.prepare_memory_tree('feature')
 
267
        self.build_ancestry(feature_tree, feature_branch)
 
268
        self.addCleanup(feature_tree.unlock)
 
269
 
 
270
        graph = mainline_tree.branch.repository.get_graph(
 
271
            feature_tree.branch.repository)
 
272
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
273
 
 
274
    def test_graph_difference(self):
 
275
        graph = self.make_graph(ancestry_1)
 
276
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
277
        self.assertEqual((set(), set(['rev1'])),
 
278
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
279
        self.assertEqual((set(['rev1']), set()),
 
280
                         graph.find_difference('rev1', NULL_REVISION))
 
281
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
282
                         graph.find_difference('rev3', 'rev2b'))
 
283
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
284
                         graph.find_difference('rev4', 'rev2b'))
 
285
 
 
286
    def test_graph_difference_criss_cross(self):
 
287
        graph = self.make_graph(criss_cross)
 
288
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
289
                         graph.find_difference('rev3a', 'rev3b'))
 
290
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
291
                         graph.find_difference('rev2a', 'rev3b'))
 
292
 
 
293
    def test_stacked_parents_provider(self):
 
294
 
 
295
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
296
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
297
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
298
        self.assertEqual([['rev4',], ['rev3']],
 
299
                         stacked.get_parents(['rev1', 'rev2']))
 
300
        self.assertEqual([['rev3',], ['rev4']],
 
301
                         stacked.get_parents(['rev2', 'rev1']))
 
302
        self.assertEqual([['rev3',], ['rev3']],
 
303
                         stacked.get_parents(['rev2', 'rev2']))
 
304
        self.assertEqual([['rev4',], ['rev4']],
 
305
                         stacked.get_parents(['rev1', 'rev1']))
 
306
 
 
307
    def test_iter_topo_order(self):
 
308
        graph = self.make_graph(ancestry_1)
 
309
        args = ['rev2a', 'rev3', 'rev1']
 
310
        topo_args = list(graph.iter_topo_order(args))
 
311
        self.assertEqual(set(args), set(topo_args))
 
312
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
 
313
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
 
314
 
 
315
    def test_is_ancestor(self):
 
316
        graph = self.make_graph(ancestry_1)
 
317
        self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
 
318
        self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
 
319
        self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
 
320
        self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
 
321
        self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
 
322
        self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
 
323
        self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
 
324
        self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
 
325
        self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
 
326
        instrumented_provider = InstrumentedParentsProvider(graph)
 
327
        instrumented_graph = _mod_graph.Graph(instrumented_provider)
 
328
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
 
329
        self.assertTrue('null:' not in instrumented_provider.calls)
 
330
 
 
331
    def test_is_ancestor_boundary(self):
 
332
        """Ensure that we avoid searching the whole graph.
 
333
        
 
334
        This requires searching through b as a common ancestor, so we
 
335
        can identify that e is common.
 
336
        """
 
337
        graph = self.make_graph(boundary)
 
338
        instrumented_provider = InstrumentedParentsProvider(graph)
 
339
        graph = _mod_graph.Graph(instrumented_provider)
 
340
        self.assertFalse(graph.is_ancestor('a', 'c'))
 
341
        self.assertTrue('null:' not in instrumented_provider.calls)
 
342
 
 
343
    def test_filter_candidate_lca(self):
 
344
        """Test filter_candidate_lca for a corner case
 
345
 
 
346
        This tests the case where we encounter the end of iteration for 'e'
 
347
        in the same pass as we discover that 'd' is an ancestor of 'e', and
 
348
        therefore 'e' can't be an lca.
 
349
 
 
350
        To compensate for different dict orderings on other Python
 
351
        implementations, we mirror 'd' and 'e' with 'b' and 'a'.
 
352
        """
 
353
        # This test is sensitive to the iteration order of dicts.  It will
 
354
        # pass incorrectly if 'e' and 'a' sort before 'c'
 
355
        #
 
356
        # NULL_REVISION
 
357
        #     / \
 
358
        #    a   e
 
359
        #    |   |
 
360
        #    b   d
 
361
        #     \ /
 
362
        #      c
 
363
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
 
364
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
 
365
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
 
366
 
 
367
    def test_heads_null(self):
 
368
        graph = self.make_graph(ancestry_1)
 
369
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
370
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
 
371
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
 
372
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
 
373
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
374
 
 
375
    def test_heads_one(self):
 
376
        # A single node will alwaya be a head
 
377
        graph = self.make_graph(ancestry_1)
 
378
        self.assertEqual(set(['null:']), graph.heads(['null:']))
 
379
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
 
380
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
 
381
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
 
382
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
 
383
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
384
 
 
385
    def test_heads_single(self):
 
386
        graph = self.make_graph(ancestry_1)
 
387
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
 
388
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
 
389
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
 
390
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
 
391
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
 
392
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
 
393
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
 
394
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
395
 
 
396
    def test_heads_two_heads(self):
 
397
        graph = self.make_graph(ancestry_1)
 
398
        self.assertEqual(set(['rev2a', 'rev2b']),
 
399
                         graph.heads(['rev2a', 'rev2b']))
 
400
        self.assertEqual(set(['rev3', 'rev2b']),
 
401
                         graph.heads(['rev3', 'rev2b']))
 
402
 
 
403
    def test_heads_criss_cross(self):
 
404
        graph = self.make_graph(criss_cross)
 
405
        self.assertEqual(set(['rev2a']),
 
406
                         graph.heads(['rev2a', 'rev1']))
 
407
        self.assertEqual(set(['rev2b']),
 
408
                         graph.heads(['rev2b', 'rev1']))
 
409
        self.assertEqual(set(['rev3a']),
 
410
                         graph.heads(['rev3a', 'rev1']))
 
411
        self.assertEqual(set(['rev3b']),
 
412
                         graph.heads(['rev3b', 'rev1']))
 
413
        self.assertEqual(set(['rev2a', 'rev2b']),
 
414
                         graph.heads(['rev2a', 'rev2b']))
 
415
        self.assertEqual(set(['rev3a']),
 
416
                         graph.heads(['rev3a', 'rev2a']))
 
417
        self.assertEqual(set(['rev3a']),
 
418
                         graph.heads(['rev3a', 'rev2b']))
 
419
        self.assertEqual(set(['rev3a']),
 
420
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
 
421
        self.assertEqual(set(['rev3b']),
 
422
                         graph.heads(['rev3b', 'rev2a']))
 
423
        self.assertEqual(set(['rev3b']),
 
424
                         graph.heads(['rev3b', 'rev2b']))
 
425
        self.assertEqual(set(['rev3b']),
 
426
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
 
427
        self.assertEqual(set(['rev3a', 'rev3b']),
 
428
                         graph.heads(['rev3a', 'rev3b']))
 
429
        self.assertEqual(set(['rev3a', 'rev3b']),
 
430
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
 
431
 
 
432
    def test_heads_shortcut(self):
 
433
        graph = self.make_graph(history_shortcut)
 
434
 
 
435
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
436
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
 
437
        self.assertEqual(set(['rev3a', 'rev3b']),
 
438
                         graph.heads(['rev3a', 'rev3b']))
 
439
        self.assertEqual(set(['rev3a', 'rev3b']),
 
440
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
 
441
        self.assertEqual(set(['rev2a', 'rev3b']),
 
442
                         graph.heads(['rev2a', 'rev3b']))
 
443
        self.assertEqual(set(['rev2c', 'rev3a']),
 
444
                         graph.heads(['rev2c', 'rev3a']))
 
445
 
 
446
    def _run_heads_break_deeper(self, graph_dict, search):
 
447
        """Run heads on a graph-as-a-dict.
 
448
        
 
449
        If the search asks for the parents of 'deeper' the test will fail.
 
450
        """
 
451
        class stub(object):
 
452
            pass
 
453
        def get_parents(keys):
 
454
            result = []
 
455
            for key in keys:
 
456
                if key == 'deeper':
 
457
                    self.fail('key deeper was accessed')
 
458
                result.append(graph_dict[key])
 
459
            return result
 
460
        an_obj = stub()
 
461
        an_obj.get_parents = get_parents
 
462
        graph = _mod_graph.Graph(an_obj)
 
463
        return graph.heads(search)
 
464
 
 
465
    def test_heads_limits_search(self):
 
466
        # test that a heads query does not search all of history
 
467
        graph_dict = {
 
468
            'left':['common'],
 
469
            'right':['common'],
 
470
            'common':['deeper'],
 
471
        }
 
472
        self.assertEqual(set(['left', 'right']),
 
473
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
 
474
 
 
475
    def test_heads_limits_search_assymetric(self):
 
476
        # test that a heads query does not search all of history
 
477
        graph_dict = {
 
478
            'left':['midleft'],
 
479
            'midleft':['common'],
 
480
            'right':['common'],
 
481
            'common':['aftercommon'],
 
482
            'aftercommon':['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_common_search_must_continue(self):
 
488
        # test that common nodes are still queried, preventing
 
489
        # all-the-way-to-origin behaviour in the following graph:
 
490
        graph_dict = {
 
491
            'h1':['shortcut', 'common1'],
 
492
            'h2':['common1'],
 
493
            'shortcut':['common2'],
 
494
            'common1':['common2'],
 
495
            'common2':['deeper'],
 
496
        }
 
497
        self.assertEqual(set(['h1', 'h2']),
 
498
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))