← 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: Vincent Ladeuil
  • Date: 2009-06-22 12:52:39 UTC
  • mto: (4471.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4472.
  • Revision ID: v.ladeuil+lp@free.fr-20090622125239-kabo9smxt9c3vnir
Use a consistent scheme for naming pyrex source files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
from bzrlib import (
18
18
    errors,
22
22
    )
23
23
from bzrlib.revision import NULL_REVISION
24
24
from bzrlib.tests import TestCaseWithMemoryTransport
 
25
from bzrlib.symbol_versioning import deprecated_in
25
26
 
26
27
 
27
28
# Ancestry 1:
237
238
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
239
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
240
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
 
                    't':['i', 's'], 'u':['s', 'j'], 
 
241
                    't':['i', 's'], 'u':['s', 'j'],
241
242
                    }
242
243
 
243
244
# Graph where different walkers will race to find the common and uncommon
283
284
#     |/
284
285
#     j
285
286
#
286
 
# y is found to be common right away, but is the start of a long series of
 
287
# x is found to be common right away, but is the start of a long series of
287
288
# common commits.
288
289
# 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 y->o to find it.
290
 
# q,n give the walker from j a common point to stop searching, as does p,f.
 
290
# unique to j at first, you have to traverse all of x->o to find it.
 
291
# q,m gives the walker from j a common point to stop searching, as does p,f.
291
292
# k-n exists so that the second pass still has nodes that are worth searching,
292
293
# rather than instantly cancelling the extra walker.
293
294
 
396
397
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
398
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
398
399
 
 
400
# A graph that shows we can shortcut finding revnos when reaching them from the
 
401
# side.
 
402
#  NULL_REVISION
 
403
#       |
 
404
#       a
 
405
#       |
 
406
#       b
 
407
#       |
 
408
#       c
 
409
#       |
 
410
#       d
 
411
#       |
 
412
#       e
 
413
#      / \
 
414
#     f   g
 
415
#     |
 
416
#     h
 
417
#     |
 
418
#     i
 
419
 
 
420
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
 
421
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
399
422
 
400
423
 
401
424
class InstrumentedParentsProvider(object):
409
432
        return self._real_parents_provider.get_parent_map(nodes)
410
433
 
411
434
 
 
435
class TestGraphBase(tests.TestCase):
 
436
 
 
437
    def make_graph(self, ancestors):
 
438
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
439
 
 
440
    def make_breaking_graph(self, ancestors, break_on):
 
441
        """Make a Graph that raises an exception if we hit a node."""
 
442
        g = self.make_graph(ancestors)
 
443
        orig_parent_map = g.get_parent_map
 
444
        def get_parent_map(keys):
 
445
            bad_keys = set(keys).intersection(break_on)
 
446
            if bad_keys:
 
447
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
 
448
            return orig_parent_map(keys)
 
449
        g.get_parent_map = get_parent_map
 
450
        return g
 
451
 
 
452
 
412
453
class TestGraph(TestCaseWithMemoryTransport):
413
454
 
414
455
    def make_graph(self, ancestors):
621
662
        self.assertEqual((set(['e']), set(['f', 'g'])),
622
663
                         graph.find_difference('e', 'f'))
623
664
 
 
665
 
624
666
    def test_stacked_parents_provider(self):
625
667
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
626
668
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
627
 
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
669
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
670
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
671
                         stacked.get_parent_map(['rev1', 'rev2']))
 
672
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
673
                         stacked.get_parent_map(['rev2', 'rev1']))
 
674
        self.assertEqual({'rev2':['rev3']},
 
675
                         stacked.get_parent_map(['rev2', 'rev2']))
 
676
        self.assertEqual({'rev1':['rev4']},
 
677
                         stacked.get_parent_map(['rev1', 'rev1']))
 
678
    
 
679
    def test_stacked_parents_provider_overlapping(self):
 
680
        # rev2 is availible in both providers.
 
681
        # 1
 
682
        # |
 
683
        # 2
 
684
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
685
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
686
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
687
        self.assertEqual({'rev2': ['rev1']},
 
688
                         stacked.get_parent_map(['rev2']))
 
689
 
 
690
    def test__stacked_parents_provider_deprecated(self):
 
691
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
692
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
693
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
 
694
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
628
695
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
629
696
                         stacked.get_parent_map(['rev1', 'rev2']))
630
697
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
658
725
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
659
726
        self.assertTrue('null:' not in instrumented_provider.calls)
660
727
 
 
728
    def test_is_between(self):
 
729
        graph = self.make_graph(ancestry_1)
 
730
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
 
731
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
 
732
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
 
733
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
 
734
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
 
735
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
 
736
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
 
737
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
 
738
 
661
739
    def test_is_ancestor_boundary(self):
662
740
        """Ensure that we avoid searching the whole graph.
663
 
        
 
741
 
664
742
        This requires searching through b as a common ancestor, so we
665
743
        can identify that e is common.
666
744
        """
686
764
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
687
765
        expected['g'] = None
688
766
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
689
 
        expected.pop('a') 
 
767
        expected.pop('a')
690
768
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
691
769
 
692
770
    def test_filter_candidate_lca(self):
794
872
 
795
873
    def _run_heads_break_deeper(self, graph_dict, search):
796
874
        """Run heads on a graph-as-a-dict.
797
 
        
 
875
 
798
876
        If the search asks for the parents of 'deeper' the test will fail.
799
877
        """
800
878
        class stub(object):
941
1019
        :param next: A callable to advance the search.
942
1020
        """
943
1021
        for seen, recipe, included_keys, starts, stops in instructions:
 
1022
            # Adjust for recipe contract changes that don't vary for all the
 
1023
            # current tests.
 
1024
            recipe = ('search',) + recipe
944
1025
            next()
945
1026
            if starts is not None:
946
1027
                search.start_searching(starts)
960
1041
        search = graph._make_breadth_first_searcher(['head'])
961
1042
        # At the start, nothing has been seen, to its all excluded:
962
1043
        result = search.get_result()
963
 
        self.assertEqual((set(['head']), set(['head']), 0),
 
1044
        self.assertEqual(('search', set(['head']), set(['head']), 0),
964
1045
            result.get_recipe())
965
1046
        self.assertEqual(set(), result.get_keys())
966
1047
        self.assertEqual(set(), search.seen)
992
1073
        search.start_searching(['head'])
993
1074
        # head has been seen:
994
1075
        result = search.get_result()
995
 
        self.assertEqual((set(['head']), set(['child']), 1),
 
1076
        self.assertEqual(('search', set(['head']), set(['child']), 1),
996
1077
            result.get_recipe())
997
1078
        self.assertEqual(set(['head']), result.get_keys())
998
1079
        self.assertEqual(set(['head']), search.seen)
1029
1110
        search = graph._make_breadth_first_searcher(['head'])
1030
1111
        expected = [
1031
1112
            # NULL_REVISION and ghost1 have not been returned
1032
 
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
 
1113
            (set(['head']),
 
1114
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1033
1115
             ['head'], None, [NULL_REVISION, 'ghost1']),
1034
1116
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1035
1117
            # next iteration.
1042
1124
        search = graph._make_breadth_first_searcher(['head'])
1043
1125
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1044
1126
 
 
1127
    def test_breadth_first_stop_searching_late(self):
 
1128
        # A client should be able to say 'stop node X' and have it excluded
 
1129
        # from the result even if X was seen in an older iteration of the
 
1130
        # search.
 
1131
        graph = self.make_graph({
 
1132
            'head':['middle'],
 
1133
            'middle':['child'],
 
1134
            'child':[NULL_REVISION],
 
1135
            NULL_REVISION:[],
 
1136
            })
 
1137
        search = graph._make_breadth_first_searcher(['head'])
 
1138
        expected = [
 
1139
            (set(['head']), (set(['head']), set(['middle']), 1),
 
1140
             ['head'], None, None),
 
1141
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
 
1142
             ['head', 'middle'], None, None),
 
1143
            # 'middle' came from the previous iteration, but we don't stop
 
1144
            # searching it until *after* advancing the searcher.
 
1145
            (set(['head', 'middle', 'child']),
 
1146
             (set(['head']), set(['middle', 'child']), 1),
 
1147
             ['head'], None, ['middle', 'child']),
 
1148
            ]
 
1149
        self.assertSeenAndResult(expected, search, search.next)
 
1150
        # using next_with_ghosts:
 
1151
        search = graph._make_breadth_first_searcher(['head'])
 
1152
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
1153
 
1045
1154
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1046
1155
        graph = self.make_graph({
1047
1156
            'head':['child', 'ghost'],
1124
1233
        self.assertRaises(StopIteration, search.next)
1125
1234
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1126
1235
        result = search.get_result()
1127
 
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1236
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1128
1237
            result.get_recipe())
1129
1238
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1130
1239
        # using next_with_ghosts:
1133
1242
        self.assertRaises(StopIteration, search.next)
1134
1243
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1135
1244
        result = search.get_result()
1136
 
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1245
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1137
1246
            result.get_recipe())
1138
1247
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1139
1248
 
1140
1249
 
1141
 
class TestFindUniqueAncestors(tests.TestCase):
1142
 
 
1143
 
    def make_graph(self, ancestors):
1144
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
1145
 
 
1146
 
    def make_breaking_graph(self, ancestors, break_on):
1147
 
        """Make a Graph that raises an exception if we hit a node."""
1148
 
        g = self.make_graph(ancestors)
1149
 
        orig_parent_map = g.get_parent_map
1150
 
        def get_parent_map(keys):
1151
 
            bad_keys = set(keys).intersection(break_on)
1152
 
            if bad_keys:
1153
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
1154
 
            return orig_parent_map(keys)
1155
 
        g.get_parent_map = get_parent_map
1156
 
        return g
 
1250
class TestFindUniqueAncestors(TestGraphBase):
1157
1251
 
1158
1252
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1159
1253
        actual = graph.find_unique_ancestors(node, common)
1228
1322
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1229
1323
 
1230
1324
 
 
1325
class TestGraphFindDistanceToNull(TestGraphBase):
 
1326
    """Test an api that should be able to compute a revno"""
 
1327
 
 
1328
    def assertFindDistance(self, revno, graph, target_id, known_ids):
 
1329
        """Assert the output of Graph.find_distance_to_null()"""
 
1330
        actual = graph.find_distance_to_null(target_id, known_ids)
 
1331
        self.assertEqual(revno, actual)
 
1332
 
 
1333
    def test_nothing_known(self):
 
1334
        graph = self.make_graph(ancestry_1)
 
1335
        self.assertFindDistance(0, graph, NULL_REVISION, [])
 
1336
        self.assertFindDistance(1, graph, 'rev1', [])
 
1337
        self.assertFindDistance(2, graph, 'rev2a', [])
 
1338
        self.assertFindDistance(2, graph, 'rev2b', [])
 
1339
        self.assertFindDistance(3, graph, 'rev3', [])
 
1340
        self.assertFindDistance(4, graph, 'rev4', [])
 
1341
 
 
1342
    def test_rev_is_ghost(self):
 
1343
        graph = self.make_graph(ancestry_1)
 
1344
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1345
                              graph.find_distance_to_null, 'rev_missing', [])
 
1346
        self.assertEqual('rev_missing', e.revision_id)
 
1347
        self.assertEqual('rev_missing', e.ghost_revision_id)
 
1348
 
 
1349
    def test_ancestor_is_ghost(self):
 
1350
        graph = self.make_graph({'rev':['parent']})
 
1351
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
 
1352
                              graph.find_distance_to_null, 'rev', [])
 
1353
        self.assertEqual('rev', e.revision_id)
 
1354
        self.assertEqual('parent', e.ghost_revision_id)
 
1355
 
 
1356
    def test_known_in_ancestry(self):
 
1357
        graph = self.make_graph(ancestry_1)
 
1358
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
 
1359
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
 
1360
 
 
1361
    def test_known_in_ancestry_limits(self):
 
1362
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1363
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
 
1364
 
 
1365
    def test_target_is_ancestor(self):
 
1366
        graph = self.make_graph(ancestry_1)
 
1367
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
 
1368
 
 
1369
    def test_target_is_ancestor_limits(self):
 
1370
        """We shouldn't search all history if we run into ourselves"""
 
1371
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
 
1372
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
 
1373
 
 
1374
    def test_target_parallel_to_known_limits(self):
 
1375
        # Even though the known revision isn't part of the other ancestry, they
 
1376
        # eventually converge
 
1377
        graph = self.make_breaking_graph(with_tail, ['a'])
 
1378
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
 
1379
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
 
1380
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
 
1381
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
 
1382
 
 
1383
 
 
1384
class TestFindMergeOrder(TestGraphBase):
 
1385
 
 
1386
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
 
1387
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
 
1388
 
 
1389
    def test_parents(self):
 
1390
        graph = self.make_graph(ancestry_1)
 
1391
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
 
1392
                                                        ['rev3', 'rev2b'])
 
1393
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
 
1394
                                                        ['rev2b', 'rev3'])
 
1395
 
 
1396
    def test_ancestors(self):
 
1397
        graph = self.make_graph(ancestry_1)
 
1398
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
 
1399
                                                        ['rev1', 'rev2b'])
 
1400
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
 
1401
                                                        ['rev2b', 'rev1'])
 
1402
 
 
1403
    def test_shortcut_one_ancestor(self):
 
1404
        # When we have enough info, we can stop searching
 
1405
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
 
1406
        # Single ancestors shortcut right away
 
1407
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
 
1408
 
 
1409
    def test_shortcut_after_one_ancestor(self):
 
1410
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
 
1411
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
 
1412
 
 
1413
 
1231
1414
class TestCachingParentsProvider(tests.TestCase):
 
1415
    """These tests run with:
 
1416
 
 
1417
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
 
1418
    ghost.
 
1419
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
 
1420
    """
1232
1421
 
1233
1422
    def setUp(self):
1234
1423
        super(TestCachingParentsProvider, self).setUp()
1253
1442
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1254
1443
        # No new calls
1255
1444
        self.assertEqual(['b'], self.inst_pp.calls)
1256
 
        self.assertEqual({'b':None}, self.caching_pp._cache)
1257
1445
 
1258
1446
    def test_get_parent_map_mixed(self):
1259
1447
        """Anything that can be returned from cache, should be"""
1270
1458
        # Use sorted because we don't care about the order, just that each is
1271
1459
        # only present 1 time.
1272
1460
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
 
1461
 
 
1462
    def test_note_missing_key(self):
 
1463
        """After noting that a key is missing it is cached."""
 
1464
        self.caching_pp.note_missing_key('b')
 
1465
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
 
1466
        self.assertEqual([], self.inst_pp.calls)
 
1467
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
 
1468
 
 
1469
 
 
1470
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
 
1471
    """Test the behaviour when parents are provided that were not requested."""
 
1472
 
 
1473
    def setUp(self):
 
1474
        super(TestCachingParentsProviderExtras, self).setUp()
 
1475
        class ExtraParentsProvider(object):
 
1476
 
 
1477
            def get_parent_map(self, keys):
 
1478
                return {'rev1': [], 'rev2': ['rev1',]}
 
1479
 
 
1480
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
 
1481
        self.caching_pp = _mod_graph.CachingParentsProvider(
 
1482
            get_parent_map=self.inst_pp.get_parent_map)
 
1483
 
 
1484
    def test_uncached(self):
 
1485
        self.caching_pp.disable_cache()
 
1486
        self.assertEqual({'rev1': []},
 
1487
                         self.caching_pp.get_parent_map(['rev1']))
 
1488
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1489
        self.assertIs(None, self.caching_pp._cache)
 
1490
 
 
1491
    def test_cache_initially_empty(self):
 
1492
        self.assertEqual({}, self.caching_pp._cache)
 
1493
 
 
1494
    def test_cached(self):
 
1495
        self.assertEqual({'rev1': []},
 
1496
                         self.caching_pp.get_parent_map(['rev1']))
 
1497
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1498
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
 
1499
                         self.caching_pp._cache)
 
1500
        self.assertEqual({'rev1': []},
 
1501
                          self.caching_pp.get_parent_map(['rev1']))
 
1502
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1503
 
 
1504
    def test_disable_cache_clears_cache(self):
 
1505
        # Put something in the cache
 
1506
        self.caching_pp.get_parent_map(['rev1'])
 
1507
        self.assertEqual(2, len(self.caching_pp._cache))
 
1508
        self.caching_pp.disable_cache()
 
1509
        self.assertIs(None, self.caching_pp._cache)
 
1510
 
 
1511
    def test_enable_cache_raises(self):
 
1512
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
 
1513
        self.assertEqual('Cache enabled when already enabled.', str(e))
 
1514
 
 
1515
    def test_cache_misses(self):
 
1516
        self.caching_pp.get_parent_map(['rev3'])
 
1517
        self.caching_pp.get_parent_map(['rev3'])
 
1518
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1519
 
 
1520
    def test_no_cache_misses(self):
 
1521
        self.caching_pp.disable_cache()
 
1522
        self.caching_pp.enable_cache(cache_misses=False)
 
1523
        self.caching_pp.get_parent_map(['rev3'])
 
1524
        self.caching_pp.get_parent_map(['rev3'])
 
1525
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
 
1526
 
 
1527
    def test_cache_extras(self):
 
1528
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
 
1529
        self.assertEqual({'rev2': ['rev1']},
 
1530
                         self.caching_pp.get_parent_map(['rev2']))
 
1531
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1532
 
 
1533
 
 
1534
class TestCollapseLinearRegions(tests.TestCase):
 
1535
 
 
1536
    def assertCollapsed(self, collapsed, original):
 
1537
        self.assertEqual(collapsed,
 
1538
                         _mod_graph.collapse_linear_regions(original))
 
1539
 
 
1540
    def test_collapse_nothing(self):
 
1541
        d = {1:[2, 3], 2:[], 3:[]}
 
1542
        self.assertCollapsed(d, d)
 
1543
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
 
1544
        self.assertCollapsed(d, d)
 
1545
 
 
1546
    def test_collapse_chain(self):
 
1547
        # Any time we have a linear chain, we should be able to collapse
 
1548
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
 
1549
        self.assertCollapsed({1:[5], 5:[]}, d)
 
1550
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
 
1551
        self.assertCollapsed({5:[1], 1:[]}, d)
 
1552
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
 
1553
        self.assertCollapsed({5:[2], 2:[]}, d)
 
1554
 
 
1555
    def test_collapse_with_multiple_children(self):
 
1556
        #    7
 
1557
        #    |
 
1558
        #    6
 
1559
        #   / \
 
1560
        #  4   5
 
1561
        #  |   |
 
1562
        #  2   3
 
1563
        #   \ /
 
1564
        #    1
 
1565
        #
 
1566
        # 4 and 5 cannot be removed because 6 has 2 children
 
1567
        # 2 and 3 cannot be removed because 1 has 2 parents
 
1568
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
 
1569
        self.assertCollapsed(d, d)
 
1570
 
 
1571
 
 
1572
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
 
1573
    """Tests for bzrlib.graph.PendingAncestryResult."""
 
1574
 
 
1575
    def test_get_keys(self):
 
1576
        builder = self.make_branch_builder('b')
 
1577
        builder.start_series()
 
1578
        builder.build_snapshot('rev-1', None, [
 
1579
            ('add', ('', 'root-id', 'directory', ''))])
 
1580
        builder.build_snapshot('rev-2', ['rev-1'], [])
 
1581
        builder.finish_series()
 
1582
        repo = builder.get_branch().repository
 
1583
        repo.lock_read()
 
1584
        self.addCleanup(repo.unlock)
 
1585
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
 
1586
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
 
1587
 
 
1588
    def test_get_keys_excludes_ghosts(self):
 
1589
        builder = self.make_branch_builder('b')
 
1590
        builder.start_series()
 
1591
        builder.build_snapshot('rev-1', None, [
 
1592
            ('add', ('', 'root-id', 'directory', ''))])
 
1593
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
 
1594
        builder.finish_series()
 
1595
        repo = builder.get_branch().repository
 
1596
        repo.lock_read()
 
1597
        self.addCleanup(repo.unlock)
 
1598
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
 
1599
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
 
1600
 
 
1601
    def test_get_keys_excludes_null(self):
 
1602
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
 
1603
        # somewhere other than the last element, which can happen in real
 
1604
        # ancestries.
 
1605
        class StubGraph(object):
 
1606
            def iter_ancestry(self, keys):
 
1607
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
 
1608
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
 
1609
        result_keys = result._get_keys(StubGraph())
 
1610
        # Only the non-null keys from the ancestry appear.
 
1611
        self.assertEqual(set(['foo']), set(result_keys))
 
1612
 
 
1613
 
 
1614
class TestPendingAncestryResultRefine(TestGraphBase):
 
1615
 
 
1616
    def test_refine(self):
 
1617
        # Used when pulling from a stacked repository, so test some revisions
 
1618
        # being satisfied from the stacking branch.
 
1619
        g = self.make_graph(
 
1620
            {"tip":["mid"], "mid":["base"], "tag":["base"],
 
1621
             "base":[NULL_REVISION], NULL_REVISION:[]})
 
1622
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
 
1623
        result = result.refine(set(['tip']), set(['mid']))
 
1624
        self.assertEqual(set(['mid', 'tag']), result.heads)
 
1625
        result = result.refine(set(['mid', 'tag', 'base']),
 
1626
            set([NULL_REVISION]))
 
1627
        self.assertEqual(set([NULL_REVISION]), result.heads)
 
1628
        self.assertTrue(result.is_empty())
 
1629
 
 
1630
 
 
1631
class TestSearchResultRefine(TestGraphBase):
 
1632
 
 
1633
    def test_refine(self):
 
1634
        # Used when pulling from a stacked repository, so test some revisions
 
1635
        # being satisfied from the stacking branch.
 
1636
        g = self.make_graph(
 
1637
            {"tip":["mid"], "mid":["base"], "tag":["base"],
 
1638
             "base":[NULL_REVISION], NULL_REVISION:[]})
 
1639
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
 
1640
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
 
1641
        result = result.refine(set(['tip']), set(['mid']))
 
1642
        recipe = result.get_recipe()
 
1643
        # We should be starting from tag (original head) and mid (seen ref)
 
1644
        self.assertEqual(set(['mid', 'tag']), recipe[1])
 
1645
        # We should be stopping at NULL (original stop) and tip (seen head)
 
1646
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
 
1647
        self.assertEqual(3, recipe[3])
 
1648
        result = result.refine(set(['mid', 'tag', 'base']),
 
1649
            set([NULL_REVISION]))
 
1650
        recipe = result.get_recipe()
 
1651
        # We should be starting from nothing (NULL was known as a cut point)
 
1652
        self.assertEqual(set([]), recipe[1])
 
1653
        # We should be stopping at NULL (original stop) and tip (seen head) and
 
1654
        # tag (seen head) and mid(seen mid-point head). We could come back and
 
1655
        # define this as not including mid, for minimal results, but it is
 
1656
        # still 'correct' to include mid, and simpler/easier.
 
1657
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
 
1658
        self.assertEqual(0, recipe[3])
 
1659
        self.assertTrue(result.is_empty())