← 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: Canonical.com Patch Queue Manager
  • Date: 2008-03-16 14:01:20 UTC
  • mfrom: (3280.2.5 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20080316140120-i3yq8yr1l66m11h7
Start 1.4 development

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
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
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
from bzrlib import (
18
18
    errors,
165
165
# Complex shortcut
166
166
# This has a failure mode in that a shortcut will find some nodes in common,
167
167
# but the common searcher won't have time to find that one branch is actually
168
 
# in common. The extra nodes at the beginning are because we want to avoid
 
168
# in common. The extra nodes at the top are because we want to avoid
169
169
# walking off the graph. Specifically, node G should be considered common, but
170
170
# is likely to be seen by M long before the common searcher finds it.
171
171
#
181
181
#     |\
182
182
#     e f
183
183
#     | |\
184
 
#     | g h
185
 
#     |/| |
186
 
#     i j |
 
184
#     i | h
 
185
#     |\| |
 
186
#     | g |
 
187
#     | | |
 
188
#     | j |
187
189
#     | | |
188
190
#     | k |
189
191
#     | | |
190
192
#     | l |
191
193
#     |/|/
192
194
#     m n
193
 
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
194
 
                    'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
195
 
                    'i':['e', 'g'], 'j':['g'], 'k':['j'],
196
 
                    'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
197
 
 
198
 
# NULL_REVISION
199
 
#     |
200
 
#     a
201
 
#     |
202
 
#     b
203
 
#     |
204
 
#     c
205
 
#     |
206
 
#     d
207
 
#     |\
208
 
#     e |
209
 
#     | |
210
 
#     f |
211
 
#     | |
212
 
#     g h
213
 
#     | |\
214
 
#     i | j
215
 
#     |\| |
216
 
#     | k |
217
 
#     | | |
218
 
#     | l |
219
 
#     | | |
220
 
#     | m |
221
 
#     | | |
222
 
#     | n |
223
 
#     | | |
224
 
#     | o |
225
 
#     | | |
226
 
#     | p |
227
 
#     | | |
228
 
#     | q |
229
 
#     | | |
230
 
#     | r |
231
 
#     | | |
232
 
#     | s |
233
 
#     | | |
234
 
#     |/|/
235
 
#     t u
236
 
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
237
 
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
 
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
 
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
 
                    't':['i', 's'], 'u':['s', 'j'],
 
195
complex_shortcut = {'d':[NULL_REVISION],
 
196
                    'x':['d'], 'y':['x'],
 
197
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
 
198
                    'i':['e'], 'j':['g'], 'k':['j'],
 
199
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
 
200
                    'o':['l'], 'p':['o'], 'q':['p'],
 
201
                    'r':['q'], 's':['r'],
241
202
                    }
242
203
 
243
 
# Graph where different walkers will race to find the common and uncommon
244
 
# nodes.
245
 
#
246
 
# NULL_REVISION
247
 
#     |
248
 
#     a
249
 
#     |
250
 
#     b
251
 
#     |
252
 
#     c
253
 
#     |
254
 
#     d
255
 
#     |\
256
 
#     e k
257
 
#     | |
258
 
#     f-+-p
259
 
#     | | |
260
 
#     | l |
261
 
#     | | |
262
 
#     | m |
263
 
#     | |\|
264
 
#     g n q
265
 
#     |\| |
266
 
#     h o |
267
 
#     |/| |
268
 
#     i r |
269
 
#     | | |
270
 
#     | s |
271
 
#     | | |
272
 
#     | t |
273
 
#     | | |
274
 
#     | u |
275
 
#     | | |
276
 
#     | v |
277
 
#     | | |
278
 
#     | w |
279
 
#     | | |
280
 
#     | x |
281
 
#     | |\|
282
 
#     | y z
283
 
#     |/
284
 
#     j
285
 
#
286
 
# x is found to be common right away, but is the start of a long series of
287
 
# common commits.
288
 
# o is actually common, but the i-j shortcut makes it look like it is actually
289
 
# unique to j at first, you have to traverse all of x->o to find it.
290
 
# q,m gives the walker from j a common point to stop searching, as does p,f.
291
 
# k-n exists so that the second pass still has nodes that are worth searching,
292
 
# rather than instantly cancelling the extra walker.
293
 
 
294
 
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
295
 
    'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
296
 
    'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
297
 
    'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
298
 
    'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
299
 
 
300
 
 
301
 
# A graph with multiple nodes unique to one side.
302
 
#
303
 
# NULL_REVISION
304
 
#     |
305
 
#     a
306
 
#     |
307
 
#     b
308
 
#     |
309
 
#     c
310
 
#     |
311
 
#     d
312
 
#     |\
313
 
#     e f
314
 
#     |\ \
315
 
#     g h i
316
 
#     |\ \ \
317
 
#     j k l m
318
 
#     | |/ x|
319
 
#     | n o p
320
 
#     | |/  |
321
 
#     | q   |
322
 
#     | |   |
323
 
#     | r   |
324
 
#     | |   |
325
 
#     | s   |
326
 
#     | |   |
327
 
#     | t   |
328
 
#     | |   |
329
 
#     | u   |
330
 
#     | |   |
331
 
#     | v   |
332
 
#     | |   |
333
 
#     | w   |
334
 
#     | |   |
335
 
#     | x   |
336
 
#     |/ \ /
337
 
#     y   z
338
 
#
339
 
 
340
 
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
341
 
    'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
342
 
    'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
343
 
    'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
344
 
    't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
345
 
    'y':['j', 'x'], 'z':['x', 'p']}
346
 
 
347
 
 
348
204
# Shortcut with extra root
349
205
# We have a long history shortcut, and an extra root, which is why we can't
350
206
# stop searchers based on seeing NULL_REVISION
396
252
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
253
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
398
254
 
399
 
# A graph that shows we can shortcut finding revnos when reaching them from the
400
 
# side.
401
 
#  NULL_REVISION
402
 
#       |
403
 
#       a
404
 
#       |
405
 
#       b
406
 
#       |
407
 
#       c
408
 
#       |
409
 
#       d
410
 
#       |
411
 
#       e
412
 
#      / \
413
 
#     f   g
414
 
#     |
415
 
#     h
416
 
#     |
417
 
#     i
418
 
 
419
 
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
420
 
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
421
255
 
422
256
 
423
257
class InstrumentedParentsProvider(object):
431
265
        return self._real_parents_provider.get_parent_map(nodes)
432
266
 
433
267
 
434
 
class TestGraphBase(tests.TestCase):
435
 
 
436
 
    def make_graph(self, ancestors):
437
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
438
 
 
439
 
    def make_breaking_graph(self, ancestors, break_on):
440
 
        """Make a Graph that raises an exception if we hit a node."""
441
 
        g = self.make_graph(ancestors)
442
 
        orig_parent_map = g.get_parent_map
443
 
        def get_parent_map(keys):
444
 
            bad_keys = set(keys).intersection(break_on)
445
 
            if bad_keys:
446
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
447
 
            return orig_parent_map(keys)
448
 
        g.get_parent_map = get_parent_map
449
 
        return g
450
 
 
451
 
 
452
268
class TestGraph(TestCaseWithMemoryTransport):
453
269
 
454
270
    def make_graph(self, ancestors):
541
357
                         graph.find_unique_lca('rev2a', 'rev2b',
542
358
                         count_steps=True))
543
359
 
544
 
    def assertRemoveDescendants(self, expected, graph, revisions):
545
 
        parents = graph.get_parent_map(revisions)
546
 
        self.assertEqual(expected,
547
 
                         graph._remove_simple_descendants(revisions, parents))
548
 
 
549
 
    def test__remove_simple_descendants(self):
550
 
        graph = self.make_graph(ancestry_1)
551
 
        self.assertRemoveDescendants(set(['rev1']), graph,
552
 
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
553
 
 
554
 
    def test__remove_simple_descendants_disjoint(self):
555
 
        graph = self.make_graph(ancestry_1)
556
 
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
557
 
            set(['rev1', 'rev3']))
558
 
 
559
 
    def test__remove_simple_descendants_chain(self):
560
 
        graph = self.make_graph(ancestry_1)
561
 
        self.assertRemoveDescendants(set(['rev1']), graph,
562
 
            set(['rev1', 'rev2a', 'rev3']))
563
 
 
564
 
    def test__remove_simple_descendants_siblings(self):
565
 
        graph = self.make_graph(ancestry_1)
566
 
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
567
 
            set(['rev2a', 'rev2b', 'rev3']))
568
 
 
569
360
    def test_unique_lca_criss_cross(self):
570
361
        """Ensure we don't pick non-unique lcas in a criss-cross"""
571
362
        graph = self.make_graph(criss_cross)
636
427
 
637
428
    def test_graph_difference_extended_history(self):
638
429
        graph = self.make_graph(extended_history_shortcut)
 
430
        self.expectFailure('find_difference cannot handle shortcuts',
 
431
            self.assertEqual, (set(['e']), set(['f'])),
 
432
                graph.find_difference('e', 'f'))
639
433
        self.assertEqual((set(['e']), set(['f'])),
640
434
                         graph.find_difference('e', 'f'))
641
435
        self.assertEqual((set(['f']), set(['e'])),
648
442
 
649
443
    def test_graph_difference_complex_shortcut(self):
650
444
        graph = self.make_graph(complex_shortcut)
651
 
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
 
445
        self.expectFailure('find_difference cannot handle shortcuts',
 
446
            self.assertEqual, (set(['m']), set(['h', 'n'])),
 
447
                graph.find_difference('m', 'n'))
 
448
        self.assertEqual((set(['m']), set(['h', 'n'])),
652
449
                         graph.find_difference('m', 'n'))
653
450
 
654
 
    def test_graph_difference_complex_shortcut2(self):
655
 
        graph = self.make_graph(complex_shortcut2)
656
 
        self.assertEqual((set(['t']), set(['j', 'u'])),
657
 
                         graph.find_difference('t', 'u'))
658
 
 
659
451
    def test_graph_difference_shortcut_extra_root(self):
660
452
        graph = self.make_graph(shortcut_extra_root)
 
453
        self.expectFailure('find_difference cannot handle shortcuts',
 
454
            self.assertEqual, (set(['e']), set(['f', 'g'])),
 
455
                graph.find_difference('e', 'f'))
661
456
        self.assertEqual((set(['e']), set(['f', 'g'])),
662
457
                         graph.find_difference('e', 'f'))
663
458
 
698
493
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
699
494
        self.assertTrue('null:' not in instrumented_provider.calls)
700
495
 
701
 
    def test_is_between(self):
702
 
        graph = self.make_graph(ancestry_1)
703
 
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
704
 
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
705
 
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
706
 
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
707
 
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
708
 
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
709
 
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
710
 
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
711
 
 
712
496
    def test_is_ancestor_boundary(self):
713
497
        """Ensure that we avoid searching the whole graph.
714
 
 
 
498
        
715
499
        This requires searching through b as a common ancestor, so we
716
500
        can identify that e is common.
717
501
        """
737
521
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
738
522
        expected['g'] = None
739
523
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
740
 
        expected.pop('a')
 
524
        expected.pop('a') 
741
525
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
742
526
 
743
527
    def test_filter_candidate_lca(self):
845
629
 
846
630
    def _run_heads_break_deeper(self, graph_dict, search):
847
631
        """Run heads on a graph-as-a-dict.
848
 
 
 
632
        
849
633
        If the search asks for the parents of 'deeper' the test will fail.
850
634
        """
851
635
        class stub(object):
992
776
        :param next: A callable to advance the search.
993
777
        """
994
778
        for seen, recipe, included_keys, starts, stops in instructions:
995
 
            # Adjust for recipe contract changes that don't vary for all the
996
 
            # current tests.
997
 
            recipe = ('search',) + recipe
998
779
            next()
999
780
            if starts is not None:
1000
781
                search.start_searching(starts)
1014
795
        search = graph._make_breadth_first_searcher(['head'])
1015
796
        # At the start, nothing has been seen, to its all excluded:
1016
797
        result = search.get_result()
1017
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
798
        self.assertEqual((set(['head']), set(['head']), 0),
1018
799
            result.get_recipe())
1019
800
        self.assertEqual(set(), result.get_keys())
1020
801
        self.assertEqual(set(), search.seen)
1046
827
        search.start_searching(['head'])
1047
828
        # head has been seen:
1048
829
        result = search.get_result()
1049
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
830
        self.assertEqual((set(['head']), set(['child']), 1),
1050
831
            result.get_recipe())
1051
832
        self.assertEqual(set(['head']), result.get_keys())
1052
833
        self.assertEqual(set(['head']), search.seen)
1083
864
        search = graph._make_breadth_first_searcher(['head'])
1084
865
        expected = [
1085
866
            # NULL_REVISION and ghost1 have not been returned
1086
 
            (set(['head']),
1087
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
867
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1088
868
             ['head'], None, [NULL_REVISION, 'ghost1']),
1089
869
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1090
870
            # next iteration.
1097
877
        search = graph._make_breadth_first_searcher(['head'])
1098
878
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1099
879
 
1100
 
    def test_breadth_first_stop_searching_late(self):
1101
 
        # A client should be able to say 'stop node X' and have it excluded
1102
 
        # from the result even if X was seen in an older iteration of the
1103
 
        # search.
1104
 
        graph = self.make_graph({
1105
 
            'head':['middle'],
1106
 
            'middle':['child'],
1107
 
            'child':[NULL_REVISION],
1108
 
            NULL_REVISION:[],
1109
 
            })
1110
 
        search = graph._make_breadth_first_searcher(['head'])
1111
 
        expected = [
1112
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1113
 
             ['head'], None, None),
1114
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1115
 
             ['head', 'middle'], None, None),
1116
 
            # 'middle' came from the previous iteration, but we don't stop
1117
 
            # searching it until *after* advancing the searcher.
1118
 
            (set(['head', 'middle', 'child']),
1119
 
             (set(['head']), set(['middle', 'child']), 1),
1120
 
             ['head'], None, ['middle', 'child']),
1121
 
            ]
1122
 
        self.assertSeenAndResult(expected, search, search.next)
1123
 
        # using next_with_ghosts:
1124
 
        search = graph._make_breadth_first_searcher(['head'])
1125
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1126
 
 
1127
880
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1128
881
        graph = self.make_graph({
1129
882
            'head':['child', 'ghost'],
1206
959
        self.assertRaises(StopIteration, search.next)
1207
960
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1208
961
        result = search.get_result()
1209
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
962
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1210
963
            result.get_recipe())
1211
964
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1212
965
        # using next_with_ghosts:
1215
968
        self.assertRaises(StopIteration, search.next)
1216
969
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1217
970
        result = search.get_result()
1218
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
971
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1219
972
            result.get_recipe())
1220
973
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1221
974
 
1222
975
 
1223
 
class TestFindUniqueAncestors(TestGraphBase):
1224
 
 
1225
 
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1226
 
        actual = graph.find_unique_ancestors(node, common)
1227
 
        self.assertEqual(expected, sorted(actual))
1228
 
 
1229
 
    def test_empty_set(self):
1230
 
        graph = self.make_graph(ancestry_1)
1231
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1232
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1233
 
        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1234
 
 
1235
 
    def test_single_node(self):
1236
 
        graph = self.make_graph(ancestry_1)
1237
 
        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1238
 
        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1239
 
        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1240
 
 
1241
 
    def test_minimal_ancestry(self):
1242
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1243
 
                                         [NULL_REVISION, 'a', 'b'])
1244
 
        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1245
 
 
1246
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1247
 
                                         ['b'])
1248
 
        self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1249
 
 
1250
 
        graph = self.make_breaking_graph(complex_shortcut,
1251
 
                                         ['a', 'b'])
1252
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1253
 
        self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1254
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1255
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1256
 
 
1257
 
    def test_in_ancestry(self):
1258
 
        graph = self.make_graph(ancestry_1)
1259
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1260
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1261
 
 
1262
 
    def test_multiple_revisions(self):
1263
 
        graph = self.make_graph(ancestry_1)
1264
 
        self.assertFindUniqueAncestors(graph,
1265
 
            ['rev4'], 'rev4', ['rev3', 'rev2b'])
1266
 
        self.assertFindUniqueAncestors(graph,
1267
 
            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1268
 
 
1269
 
    def test_complex_shortcut(self):
1270
 
        graph = self.make_graph(complex_shortcut)
1271
 
        self.assertFindUniqueAncestors(graph,
1272
 
            ['h', 'n'], 'n', ['m'])
1273
 
        self.assertFindUniqueAncestors(graph,
1274
 
            ['e', 'i', 'm'], 'm', ['n'])
1275
 
 
1276
 
    def test_complex_shortcut2(self):
1277
 
        graph = self.make_graph(complex_shortcut2)
1278
 
        self.assertFindUniqueAncestors(graph,
1279
 
            ['j', 'u'], 'u', ['t'])
1280
 
        self.assertFindUniqueAncestors(graph,
1281
 
            ['t'], 't', ['u'])
1282
 
 
1283
 
    def test_multiple_interesting_unique(self):
1284
 
        graph = self.make_graph(multiple_interesting_unique)
1285
 
        self.assertFindUniqueAncestors(graph,
1286
 
            ['j', 'y'], 'y', ['z'])
1287
 
        self.assertFindUniqueAncestors(graph,
1288
 
            ['p', 'z'], 'z', ['y'])
1289
 
 
1290
 
    def test_racing_shortcuts(self):
1291
 
        graph = self.make_graph(racing_shortcuts)
1292
 
        self.assertFindUniqueAncestors(graph,
1293
 
            ['p', 'q', 'z'], 'z', ['y'])
1294
 
        self.assertFindUniqueAncestors(graph,
1295
 
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1296
 
 
1297
 
 
1298
 
class TestGraphFindDistanceToNull(TestGraphBase):
1299
 
    """Test an api that should be able to compute a revno"""
1300
 
 
1301
 
    def assertFindDistance(self, revno, graph, target_id, known_ids):
1302
 
        """Assert the output of Graph.find_distance_to_null()"""
1303
 
        actual = graph.find_distance_to_null(target_id, known_ids)
1304
 
        self.assertEqual(revno, actual)
1305
 
 
1306
 
    def test_nothing_known(self):
1307
 
        graph = self.make_graph(ancestry_1)
1308
 
        self.assertFindDistance(0, graph, NULL_REVISION, [])
1309
 
        self.assertFindDistance(1, graph, 'rev1', [])
1310
 
        self.assertFindDistance(2, graph, 'rev2a', [])
1311
 
        self.assertFindDistance(2, graph, 'rev2b', [])
1312
 
        self.assertFindDistance(3, graph, 'rev3', [])
1313
 
        self.assertFindDistance(4, graph, 'rev4', [])
1314
 
 
1315
 
    def test_rev_is_ghost(self):
1316
 
        graph = self.make_graph(ancestry_1)
1317
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1318
 
                              graph.find_distance_to_null, 'rev_missing', [])
1319
 
        self.assertEqual('rev_missing', e.revision_id)
1320
 
        self.assertEqual('rev_missing', e.ghost_revision_id)
1321
 
 
1322
 
    def test_ancestor_is_ghost(self):
1323
 
        graph = self.make_graph({'rev':['parent']})
1324
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1325
 
                              graph.find_distance_to_null, 'rev', [])
1326
 
        self.assertEqual('rev', e.revision_id)
1327
 
        self.assertEqual('parent', e.ghost_revision_id)
1328
 
 
1329
 
    def test_known_in_ancestry(self):
1330
 
        graph = self.make_graph(ancestry_1)
1331
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1332
 
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1333
 
 
1334
 
    def test_known_in_ancestry_limits(self):
1335
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1336
 
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1337
 
 
1338
 
    def test_target_is_ancestor(self):
1339
 
        graph = self.make_graph(ancestry_1)
1340
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1341
 
 
1342
 
    def test_target_is_ancestor_limits(self):
1343
 
        """We shouldn't search all history if we run into ourselves"""
1344
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1345
 
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1346
 
 
1347
 
    def test_target_parallel_to_known_limits(self):
1348
 
        # Even though the known revision isn't part of the other ancestry, they
1349
 
        # eventually converge
1350
 
        graph = self.make_breaking_graph(with_tail, ['a'])
1351
 
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
1352
 
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
1353
 
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
1354
 
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1355
 
 
1356
 
 
1357
 
class TestFindMergeOrder(TestGraphBase):
1358
 
 
1359
 
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
1360
 
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1361
 
 
1362
 
    def test_parents(self):
1363
 
        graph = self.make_graph(ancestry_1)
1364
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1365
 
                                                        ['rev3', 'rev2b'])
1366
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1367
 
                                                        ['rev2b', 'rev3'])
1368
 
 
1369
 
    def test_ancestors(self):
1370
 
        graph = self.make_graph(ancestry_1)
1371
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1372
 
                                                        ['rev1', 'rev2b'])
1373
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1374
 
                                                        ['rev2b', 'rev1'])
1375
 
 
1376
 
    def test_shortcut_one_ancestor(self):
1377
 
        # When we have enough info, we can stop searching
1378
 
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1379
 
        # Single ancestors shortcut right away
1380
 
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1381
 
 
1382
 
    def test_shortcut_after_one_ancestor(self):
1383
 
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1384
 
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1385
 
 
1386
 
 
1387
976
class TestCachingParentsProvider(tests.TestCase):
1388
 
    """These tests run with:
1389
 
 
1390
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1391
 
    ghost.
1392
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1393
 
    """
1394
977
 
1395
978
    def setUp(self):
1396
979
        super(TestCachingParentsProvider, self).setUp()
1415
998
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1416
999
        # No new calls
1417
1000
        self.assertEqual(['b'], self.inst_pp.calls)
 
1001
        self.assertEqual({'b':None}, self.caching_pp._cache)
1418
1002
 
1419
1003
    def test_get_parent_map_mixed(self):
1420
1004
        """Anything that can be returned from cache, should be"""
1431
1015
        # Use sorted because we don't care about the order, just that each is
1432
1016
        # only present 1 time.
1433
1017
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1434
 
 
1435
 
    def test_note_missing_key(self):
1436
 
        """After noting that a key is missing it is cached."""
1437
 
        self.caching_pp.note_missing_key('b')
1438
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1439
 
        self.assertEqual([], self.inst_pp.calls)
1440
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1441
 
 
1442
 
 
1443
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1444
 
    """Test the behaviour when parents are provided that were not requested."""
1445
 
 
1446
 
    def setUp(self):
1447
 
        super(TestCachingParentsProviderExtras, self).setUp()
1448
 
        class ExtraParentsProvider(object):
1449
 
 
1450
 
            def get_parent_map(self, keys):
1451
 
                return {'rev1': [], 'rev2': ['rev1',]}
1452
 
 
1453
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1454
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1455
 
            get_parent_map=self.inst_pp.get_parent_map)
1456
 
 
1457
 
    def test_uncached(self):
1458
 
        self.caching_pp.disable_cache()
1459
 
        self.assertEqual({'rev1': []},
1460
 
                         self.caching_pp.get_parent_map(['rev1']))
1461
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1462
 
        self.assertIs(None, self.caching_pp._cache)
1463
 
 
1464
 
    def test_cache_initially_empty(self):
1465
 
        self.assertEqual({}, self.caching_pp._cache)
1466
 
 
1467
 
    def test_cached(self):
1468
 
        self.assertEqual({'rev1': []},
1469
 
                         self.caching_pp.get_parent_map(['rev1']))
1470
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1471
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1472
 
                         self.caching_pp._cache)
1473
 
        self.assertEqual({'rev1': []},
1474
 
                          self.caching_pp.get_parent_map(['rev1']))
1475
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1476
 
 
1477
 
    def test_disable_cache_clears_cache(self):
1478
 
        # Put something in the cache
1479
 
        self.caching_pp.get_parent_map(['rev1'])
1480
 
        self.assertEqual(2, len(self.caching_pp._cache))
1481
 
        self.caching_pp.disable_cache()
1482
 
        self.assertIs(None, self.caching_pp._cache)
1483
 
 
1484
 
    def test_enable_cache_raises(self):
1485
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1486
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1487
 
 
1488
 
    def test_cache_misses(self):
1489
 
        self.caching_pp.get_parent_map(['rev3'])
1490
 
        self.caching_pp.get_parent_map(['rev3'])
1491
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1492
 
 
1493
 
    def test_no_cache_misses(self):
1494
 
        self.caching_pp.disable_cache()
1495
 
        self.caching_pp.enable_cache(cache_misses=False)
1496
 
        self.caching_pp.get_parent_map(['rev3'])
1497
 
        self.caching_pp.get_parent_map(['rev3'])
1498
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1499
 
 
1500
 
    def test_cache_extras(self):
1501
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1502
 
        self.assertEqual({'rev2': ['rev1']},
1503
 
                         self.caching_pp.get_parent_map(['rev2']))
1504
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1505
 
 
1506
 
 
1507
 
class TestCollapseLinearRegions(tests.TestCase):
1508
 
 
1509
 
    def assertCollapsed(self, collapsed, original):
1510
 
        self.assertEqual(collapsed,
1511
 
                         _mod_graph.collapse_linear_regions(original))
1512
 
 
1513
 
    def test_collapse_nothing(self):
1514
 
        d = {1:[2, 3], 2:[], 3:[]}
1515
 
        self.assertCollapsed(d, d)
1516
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1517
 
        self.assertCollapsed(d, d)
1518
 
 
1519
 
    def test_collapse_chain(self):
1520
 
        # Any time we have a linear chain, we should be able to collapse
1521
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1522
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1523
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1524
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1525
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1526
 
        self.assertCollapsed({5:[2], 2:[]}, d)
1527
 
 
1528
 
    def test_collapse_with_multiple_children(self):
1529
 
        #    7
1530
 
        #    |
1531
 
        #    6
1532
 
        #   / \
1533
 
        #  4   5
1534
 
        #  |   |
1535
 
        #  2   3
1536
 
        #   \ /
1537
 
        #    1
1538
 
        #
1539
 
        # 4 and 5 cannot be removed because 6 has 2 children
1540
 
        # 2 and 3 cannot be removed because 1 has 2 parents
1541
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1542
 
        self.assertCollapsed(d, d)
1543
 
 
1544
 
 
1545
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1546
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1547
 
 
1548
 
    def test_get_keys(self):
1549
 
        builder = self.make_branch_builder('b')
1550
 
        builder.start_series()
1551
 
        builder.build_snapshot('rev-1', None, [
1552
 
            ('add', ('', 'root-id', 'directory', ''))])
1553
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1554
 
        builder.finish_series()
1555
 
        repo = builder.get_branch().repository
1556
 
        repo.lock_read()
1557
 
        self.addCleanup(repo.unlock)
1558
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1559
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1560
 
 
1561
 
    def test_get_keys_excludes_ghosts(self):
1562
 
        builder = self.make_branch_builder('b')
1563
 
        builder.start_series()
1564
 
        builder.build_snapshot('rev-1', None, [
1565
 
            ('add', ('', 'root-id', 'directory', ''))])
1566
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1567
 
        builder.finish_series()
1568
 
        repo = builder.get_branch().repository
1569
 
        repo.lock_read()
1570
 
        self.addCleanup(repo.unlock)
1571
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1572
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1573
 
 
1574
 
    def test_get_keys_excludes_null(self):
1575
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1576
 
        # somewhere other than the last element, which can happen in real
1577
 
        # ancestries.
1578
 
        class StubGraph(object):
1579
 
            def iter_ancestry(self, keys):
1580
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1581
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1582
 
        result_keys = result._get_keys(StubGraph())
1583
 
        # Only the non-null keys from the ancestry appear.
1584
 
        self.assertEqual(set(['foo']), set(result_keys))
1585
 
 
1586
 
 
1587
 
class TestPendingAncestryResultRefine(TestGraphBase):
1588
 
 
1589
 
    def test_refine(self):
1590
 
        # Used when pulling from a stacked repository, so test some revisions
1591
 
        # being satisfied from the stacking branch.
1592
 
        g = self.make_graph(
1593
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1594
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1595
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1596
 
        result = result.refine(set(['tip']), set(['mid']))
1597
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1598
 
        result = result.refine(set(['mid', 'tag', 'base']),
1599
 
            set([NULL_REVISION]))
1600
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1601
 
        self.assertTrue(result.is_empty())
1602
 
 
1603
 
 
1604
 
class TestSearchResultRefine(TestGraphBase):
1605
 
 
1606
 
    def test_refine(self):
1607
 
        # Used when pulling from a stacked repository, so test some revisions
1608
 
        # being satisfied from the stacking branch.
1609
 
        g = self.make_graph(
1610
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1611
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1612
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1613
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1614
 
        result = result.refine(set(['tip']), set(['mid']))
1615
 
        recipe = result.get_recipe()
1616
 
        # We should be starting from tag (original head) and mid (seen ref)
1617
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1618
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1619
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1620
 
        self.assertEqual(3, recipe[3])
1621
 
        result = result.refine(set(['mid', 'tag', 'base']),
1622
 
            set([NULL_REVISION]))
1623
 
        recipe = result.get_recipe()
1624
 
        # We should be starting from nothing (NULL was known as a cut point)
1625
 
        self.assertEqual(set([]), recipe[1])
1626
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1627
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1628
 
        # define this as not including mid, for minimal results, but it is
1629
 
        # still 'correct' to include mid, and simpler/easier.
1630
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1631
 
        self.assertEqual(0, recipe[3])
1632
 
        self.assertTrue(result.is_empty())