/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-16 01:28:59 UTC
  • mto: This revision was merged to the branch mainline in revision 3015.
  • Revision ID: robertc@robertcollins.net-20071116012859-909bq5as99bj7hx2
Change check and reconcile to use the new _generate_text_key_index rather
than a _RevisionTextVersionCache in calculating the correct per-file
parent information. This exposed some test errors which got changed, and
reporting some aspects of inventory-text mismatches become harder to
report (but easier to calculate for when we do start correcting it).

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