← 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: Andrew Bennetts
  • Date: 2008-07-03 07:56:02 UTC
  • mto: This revision was merged to the branch mainline in revision 3520.
  • Revision ID: andrew.bennetts@canonical.com-20080703075602-8n055qsfkjijcz6i
Better tests for {pre,post}_change_branch_tip hooks.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007 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., 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,
19
19
    graph as _mod_graph,
 
20
    symbol_versioning,
20
21
    tests,
21
22
    )
22
23
from bzrlib.revision import NULL_REVISION
23
24
from bzrlib.tests import TestCaseWithMemoryTransport
24
 
from bzrlib.symbol_versioning import deprecated_in
25
25
 
26
26
 
27
27
# Ancestry 1:
237
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
 
                    't':['i', 's'], 'u':['s', 'j'],
 
240
                    't':['i', 's'], 'u':['s', 'j'], 
241
241
                    }
242
242
 
243
243
# Graph where different walkers will race to find the common and uncommon
525
525
        graph = self.make_graph(history_shortcut)
526
526
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
527
527
 
528
 
    def test_lefthand_distance_smoke(self):
529
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
530
 
        graph = self.make_graph(history_shortcut)
531
 
        distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
532
 
        self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
533
 
 
534
 
    def test_lefthand_distance_ghosts(self):
535
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
536
 
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
537
 
        graph = self.make_graph(nodes)
538
 
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
539
 
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
540
 
 
541
528
    def test_recursive_unique_lca(self):
542
529
        """Test finding a unique least common ancestor.
543
530
 
674
661
        self.assertEqual((set(['e']), set(['f', 'g'])),
675
662
                         graph.find_difference('e', 'f'))
676
663
 
677
 
 
678
664
    def test_stacked_parents_provider(self):
679
665
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
680
666
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
681
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
667
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
682
668
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
683
669
                         stacked.get_parent_map(['rev1', 'rev2']))
684
670
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
687
673
                         stacked.get_parent_map(['rev2', 'rev2']))
688
674
        self.assertEqual({'rev1':['rev4']},
689
675
                         stacked.get_parent_map(['rev1', 'rev1']))
690
 
    
691
 
    def test_stacked_parents_provider_overlapping(self):
692
 
        # rev2 is availible in both providers.
693
 
        # 1
694
 
        # |
695
 
        # 2
696
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
697
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
699
 
        self.assertEqual({'rev2': ['rev1']},
700
 
                         stacked.get_parent_map(['rev2']))
701
676
 
702
677
    def test_iter_topo_order(self):
703
678
        graph = self.make_graph(ancestry_1)
723
698
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
724
699
        self.assertTrue('null:' not in instrumented_provider.calls)
725
700
 
726
 
    def test_is_between(self):
727
 
        graph = self.make_graph(ancestry_1)
728
 
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
729
 
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
730
 
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
731
 
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
732
 
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
733
 
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
734
 
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
735
 
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
736
 
 
737
701
    def test_is_ancestor_boundary(self):
738
702
        """Ensure that we avoid searching the whole graph.
739
 
 
 
703
        
740
704
        This requires searching through b as a common ancestor, so we
741
705
        can identify that e is common.
742
706
        """
762
726
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
763
727
        expected['g'] = None
764
728
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
765
 
        expected.pop('a')
 
729
        expected.pop('a') 
766
730
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
767
731
 
768
732
    def test_filter_candidate_lca(self):
870
834
 
871
835
    def _run_heads_break_deeper(self, graph_dict, search):
872
836
        """Run heads on a graph-as-a-dict.
873
 
 
 
837
        
874
838
        If the search asks for the parents of 'deeper' the test will fail.
875
839
        """
876
840
        class stub(object):
1017
981
        :param next: A callable to advance the search.
1018
982
        """
1019
983
        for seen, recipe, included_keys, starts, stops in instructions:
1020
 
            # Adjust for recipe contract changes that don't vary for all the
1021
 
            # current tests.
1022
 
            recipe = ('search',) + recipe
1023
984
            next()
1024
985
            if starts is not None:
1025
986
                search.start_searching(starts)
1039
1000
        search = graph._make_breadth_first_searcher(['head'])
1040
1001
        # At the start, nothing has been seen, to its all excluded:
1041
1002
        result = search.get_result()
1042
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
1003
        self.assertEqual((set(['head']), set(['head']), 0),
1043
1004
            result.get_recipe())
1044
1005
        self.assertEqual(set(), result.get_keys())
1045
1006
        self.assertEqual(set(), search.seen)
1071
1032
        search.start_searching(['head'])
1072
1033
        # head has been seen:
1073
1034
        result = search.get_result()
1074
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
1035
        self.assertEqual((set(['head']), set(['child']), 1),
1075
1036
            result.get_recipe())
1076
1037
        self.assertEqual(set(['head']), result.get_keys())
1077
1038
        self.assertEqual(set(['head']), search.seen)
1108
1069
        search = graph._make_breadth_first_searcher(['head'])
1109
1070
        expected = [
1110
1071
            # NULL_REVISION and ghost1 have not been returned
1111
 
            (set(['head']),
1112
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1072
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1113
1073
             ['head'], None, [NULL_REVISION, 'ghost1']),
1114
1074
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1115
1075
            # next iteration.
1122
1082
        search = graph._make_breadth_first_searcher(['head'])
1123
1083
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1124
1084
 
1125
 
    def test_breadth_first_stop_searching_late(self):
1126
 
        # A client should be able to say 'stop node X' and have it excluded
1127
 
        # from the result even if X was seen in an older iteration of the
1128
 
        # search.
1129
 
        graph = self.make_graph({
1130
 
            'head':['middle'],
1131
 
            'middle':['child'],
1132
 
            'child':[NULL_REVISION],
1133
 
            NULL_REVISION:[],
1134
 
            })
1135
 
        search = graph._make_breadth_first_searcher(['head'])
1136
 
        expected = [
1137
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1138
 
             ['head'], None, None),
1139
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1140
 
             ['head', 'middle'], None, None),
1141
 
            # 'middle' came from the previous iteration, but we don't stop
1142
 
            # searching it until *after* advancing the searcher.
1143
 
            (set(['head', 'middle', 'child']),
1144
 
             (set(['head']), set(['middle', 'child']), 1),
1145
 
             ['head'], None, ['middle', 'child']),
1146
 
            ]
1147
 
        self.assertSeenAndResult(expected, search, search.next)
1148
 
        # using next_with_ghosts:
1149
 
        search = graph._make_breadth_first_searcher(['head'])
1150
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1151
 
 
1152
1085
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1153
1086
        graph = self.make_graph({
1154
1087
            'head':['child', 'ghost'],
1231
1164
        self.assertRaises(StopIteration, search.next)
1232
1165
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1233
1166
        result = search.get_result()
1234
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1167
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1235
1168
            result.get_recipe())
1236
1169
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1237
1170
        # using next_with_ghosts:
1240
1173
        self.assertRaises(StopIteration, search.next)
1241
1174
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1242
1175
        result = search.get_result()
1243
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1176
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1244
1177
            result.get_recipe())
1245
1178
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1246
1179
 
1379
1312
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1380
1313
 
1381
1314
 
1382
 
class TestFindMergeOrder(TestGraphBase):
1383
 
 
1384
 
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
1385
 
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1386
 
 
1387
 
    def test_parents(self):
1388
 
        graph = self.make_graph(ancestry_1)
1389
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1390
 
                                                        ['rev3', 'rev2b'])
1391
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1392
 
                                                        ['rev2b', 'rev3'])
1393
 
 
1394
 
    def test_ancestors(self):
1395
 
        graph = self.make_graph(ancestry_1)
1396
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1397
 
                                                        ['rev1', 'rev2b'])
1398
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1399
 
                                                        ['rev2b', 'rev1'])
1400
 
 
1401
 
    def test_shortcut_one_ancestor(self):
1402
 
        # When we have enough info, we can stop searching
1403
 
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1404
 
        # Single ancestors shortcut right away
1405
 
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1406
 
 
1407
 
    def test_shortcut_after_one_ancestor(self):
1408
 
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1409
 
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1410
 
 
1411
 
 
1412
 
class TestFindDescendants(TestGraphBase):
1413
 
 
1414
 
    def test_find_descendants_rev1_rev3(self):
1415
 
        graph = self.make_graph(ancestry_1)
1416
 
        descendants = graph.find_descendants('rev1', 'rev3')
1417
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1418
 
 
1419
 
    def test_find_descendants_rev1_rev4(self):
1420
 
        graph = self.make_graph(ancestry_1)
1421
 
        descendants = graph.find_descendants('rev1', 'rev4')
1422
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1423
 
                         descendants)
1424
 
 
1425
 
    def test_find_descendants_rev2a_rev4(self):
1426
 
        graph = self.make_graph(ancestry_1)
1427
 
        descendants = graph.find_descendants('rev2a', 'rev4')
1428
 
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1429
 
 
1430
 
class TestFindLefthandMerger(TestGraphBase):
1431
 
 
1432
 
    def check_merger(self, result, ancestry, merged, tip):
1433
 
        graph = self.make_graph(ancestry)
1434
 
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1435
 
 
1436
 
    def test_find_lefthand_merger_rev2b(self):
1437
 
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1438
 
 
1439
 
    def test_find_lefthand_merger_rev2a(self):
1440
 
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1441
 
 
1442
 
    def test_find_lefthand_merger_rev4(self):
1443
 
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1444
 
 
1445
 
    def test_find_lefthand_merger_f(self):
1446
 
        self.check_merger('i', complex_shortcut, 'f', 'm')
1447
 
 
1448
 
    def test_find_lefthand_merger_g(self):
1449
 
        self.check_merger('i', complex_shortcut, 'g', 'm')
1450
 
 
1451
 
    def test_find_lefthand_merger_h(self):
1452
 
        self.check_merger('n', complex_shortcut, 'h', 'n')
1453
 
 
1454
 
 
1455
 
class TestGetChildMap(TestGraphBase):
1456
 
 
1457
 
    def test_get_child_map(self):
1458
 
        graph = self.make_graph(ancestry_1)
1459
 
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1460
 
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1461
 
                          'rev2a': ['rev3'],
1462
 
                          'rev2b': ['rev4'],
1463
 
                          'rev3': ['rev4']},
1464
 
                          child_map)
1465
 
 
1466
 
 
1467
1315
class TestCachingParentsProvider(tests.TestCase):
1468
 
    """These tests run with:
1469
 
 
1470
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1471
 
    ghost.
1472
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1473
 
    """
1474
1316
 
1475
1317
    def setUp(self):
1476
1318
        super(TestCachingParentsProvider, self).setUp()
1495
1337
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1496
1338
        # No new calls
1497
1339
        self.assertEqual(['b'], self.inst_pp.calls)
 
1340
        self.assertEqual({'b':None}, self.caching_pp._cache)
1498
1341
 
1499
1342
    def test_get_parent_map_mixed(self):
1500
1343
        """Anything that can be returned from cache, should be"""
1511
1354
        # Use sorted because we don't care about the order, just that each is
1512
1355
        # only present 1 time.
1513
1356
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1514
 
 
1515
 
    def test_note_missing_key(self):
1516
 
        """After noting that a key is missing it is cached."""
1517
 
        self.caching_pp.note_missing_key('b')
1518
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1519
 
        self.assertEqual([], self.inst_pp.calls)
1520
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1521
 
 
1522
 
 
1523
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1524
 
    """Test the behaviour when parents are provided that were not requested."""
1525
 
 
1526
 
    def setUp(self):
1527
 
        super(TestCachingParentsProviderExtras, self).setUp()
1528
 
        class ExtraParentsProvider(object):
1529
 
 
1530
 
            def get_parent_map(self, keys):
1531
 
                return {'rev1': [], 'rev2': ['rev1',]}
1532
 
 
1533
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1534
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1535
 
            get_parent_map=self.inst_pp.get_parent_map)
1536
 
 
1537
 
    def test_uncached(self):
1538
 
        self.caching_pp.disable_cache()
1539
 
        self.assertEqual({'rev1': []},
1540
 
                         self.caching_pp.get_parent_map(['rev1']))
1541
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1542
 
        self.assertIs(None, self.caching_pp._cache)
1543
 
 
1544
 
    def test_cache_initially_empty(self):
1545
 
        self.assertEqual({}, self.caching_pp._cache)
1546
 
 
1547
 
    def test_cached(self):
1548
 
        self.assertEqual({'rev1': []},
1549
 
                         self.caching_pp.get_parent_map(['rev1']))
1550
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1551
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1552
 
                         self.caching_pp._cache)
1553
 
        self.assertEqual({'rev1': []},
1554
 
                          self.caching_pp.get_parent_map(['rev1']))
1555
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1556
 
 
1557
 
    def test_disable_cache_clears_cache(self):
1558
 
        # Put something in the cache
1559
 
        self.caching_pp.get_parent_map(['rev1'])
1560
 
        self.assertEqual(2, len(self.caching_pp._cache))
1561
 
        self.caching_pp.disable_cache()
1562
 
        self.assertIs(None, self.caching_pp._cache)
1563
 
 
1564
 
    def test_enable_cache_raises(self):
1565
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1566
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1567
 
 
1568
 
    def test_cache_misses(self):
1569
 
        self.caching_pp.get_parent_map(['rev3'])
1570
 
        self.caching_pp.get_parent_map(['rev3'])
1571
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1572
 
 
1573
 
    def test_no_cache_misses(self):
1574
 
        self.caching_pp.disable_cache()
1575
 
        self.caching_pp.enable_cache(cache_misses=False)
1576
 
        self.caching_pp.get_parent_map(['rev3'])
1577
 
        self.caching_pp.get_parent_map(['rev3'])
1578
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1579
 
 
1580
 
    def test_cache_extras(self):
1581
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1582
 
        self.assertEqual({'rev2': ['rev1']},
1583
 
                         self.caching_pp.get_parent_map(['rev2']))
1584
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1585
 
 
1586
 
 
1587
 
class TestCollapseLinearRegions(tests.TestCase):
1588
 
 
1589
 
    def assertCollapsed(self, collapsed, original):
1590
 
        self.assertEqual(collapsed,
1591
 
                         _mod_graph.collapse_linear_regions(original))
1592
 
 
1593
 
    def test_collapse_nothing(self):
1594
 
        d = {1:[2, 3], 2:[], 3:[]}
1595
 
        self.assertCollapsed(d, d)
1596
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1597
 
        self.assertCollapsed(d, d)
1598
 
 
1599
 
    def test_collapse_chain(self):
1600
 
        # Any time we have a linear chain, we should be able to collapse
1601
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1602
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1603
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1604
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1605
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1606
 
        self.assertCollapsed({5:[2], 2:[]}, d)
1607
 
 
1608
 
    def test_collapse_with_multiple_children(self):
1609
 
        #    7
1610
 
        #    |
1611
 
        #    6
1612
 
        #   / \
1613
 
        #  4   5
1614
 
        #  |   |
1615
 
        #  2   3
1616
 
        #   \ /
1617
 
        #    1
1618
 
        #
1619
 
        # 4 and 5 cannot be removed because 6 has 2 children
1620
 
        # 2 and 3 cannot be removed because 1 has 2 parents
1621
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1622
 
        self.assertCollapsed(d, d)
1623
 
 
1624
 
 
1625
 
class TestGraphThunkIdsToKeys(tests.TestCase):
1626
 
 
1627
 
    def test_heads(self):
1628
 
        # A
1629
 
        # |\
1630
 
        # B C
1631
 
        # |/
1632
 
        # D
1633
 
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1634
 
             ('B',): [('A',)], ('A',): []}
1635
 
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1636
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1637
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1638
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1639
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1640
 
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1641
 
 
1642
 
    def test_add_node(self):
1643
 
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1644
 
        g = _mod_graph.KnownGraph(d)
1645
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1646
 
        graph_thunk.add_node("D", ["A", "C"])
1647
 
        self.assertEqual(['B', 'D'],
1648
 
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
1649
 
 
1650
 
 
1651
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1652
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1653
 
 
1654
 
    def test_get_keys(self):
1655
 
        builder = self.make_branch_builder('b')
1656
 
        builder.start_series()
1657
 
        builder.build_snapshot('rev-1', None, [
1658
 
            ('add', ('', 'root-id', 'directory', ''))])
1659
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1660
 
        builder.finish_series()
1661
 
        repo = builder.get_branch().repository
1662
 
        repo.lock_read()
1663
 
        self.addCleanup(repo.unlock)
1664
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1665
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1666
 
 
1667
 
    def test_get_keys_excludes_ghosts(self):
1668
 
        builder = self.make_branch_builder('b')
1669
 
        builder.start_series()
1670
 
        builder.build_snapshot('rev-1', None, [
1671
 
            ('add', ('', 'root-id', 'directory', ''))])
1672
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1673
 
        builder.finish_series()
1674
 
        repo = builder.get_branch().repository
1675
 
        repo.lock_read()
1676
 
        self.addCleanup(repo.unlock)
1677
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1678
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1679
 
 
1680
 
    def test_get_keys_excludes_null(self):
1681
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1682
 
        # somewhere other than the last element, which can happen in real
1683
 
        # ancestries.
1684
 
        class StubGraph(object):
1685
 
            def iter_ancestry(self, keys):
1686
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1687
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1688
 
        result_keys = result._get_keys(StubGraph())
1689
 
        # Only the non-null keys from the ancestry appear.
1690
 
        self.assertEqual(set(['foo']), set(result_keys))
1691
 
 
1692
 
 
1693
 
class TestPendingAncestryResultRefine(TestGraphBase):
1694
 
 
1695
 
    def test_refine(self):
1696
 
        # Used when pulling from a stacked repository, so test some revisions
1697
 
        # being satisfied from the stacking branch.
1698
 
        g = self.make_graph(
1699
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1700
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1701
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1702
 
        result = result.refine(set(['tip']), set(['mid']))
1703
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1704
 
        result = result.refine(set(['mid', 'tag', 'base']),
1705
 
            set([NULL_REVISION]))
1706
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1707
 
        self.assertTrue(result.is_empty())
1708
 
 
1709
 
 
1710
 
class TestSearchResultRefine(TestGraphBase):
1711
 
 
1712
 
    def test_refine(self):
1713
 
        # Used when pulling from a stacked repository, so test some revisions
1714
 
        # being satisfied from the stacking branch.
1715
 
        g = self.make_graph(
1716
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1717
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1718
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1719
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1720
 
        result = result.refine(set(['tip']), set(['mid']))
1721
 
        recipe = result.get_recipe()
1722
 
        # We should be starting from tag (original head) and mid (seen ref)
1723
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1724
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1725
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1726
 
        self.assertEqual(3, recipe[3])
1727
 
        result = result.refine(set(['mid', 'tag', 'base']),
1728
 
            set([NULL_REVISION]))
1729
 
        recipe = result.get_recipe()
1730
 
        # We should be starting from nothing (NULL was known as a cut point)
1731
 
        self.assertEqual(set([]), recipe[1])
1732
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1733
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1734
 
        # define this as not including mid, for minimal results, but it is
1735
 
        # still 'correct' to include mid, and simpler/easier.
1736
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1737
 
        self.assertEqual(0, recipe[3])
1738
 
        self.assertTrue(result.is_empty())