← 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: 2011-08-17 18:13:57 UTC
  • mfrom: (5268.7.29 transport-segments)
  • Revision ID: pqm@pqm.ubuntu.com-20110817181357-y5q5eth1hk8bl3om
(jelmer) Allow specifying the colocated branch to use in the branch URL,
 and retrieving the branch name using ControlDir._get_selected_branch.
 (Jelmer Vernooij)

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