/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Andrew Bennetts
  • Date: 2008-08-12 14:53:26 UTC
  • mto: This revision was merged to the branch mainline in revision 3624.
  • Revision ID: andrew.bennetts@canonical.com-20080812145326-yx693x2jc4rcovb7
Move the notes on writing tests out of HACKING into a new file, and improve
them.

Many of the testing notes in the HACKING file were in duplicated in two places
in that file!  This change removes that duplication.  It also adds new sections
on “Where should I put a new test?” and “TestCase and its subclasses”, and
others like “Test feature dependencies” have been expanded.  The whole document
has generally been edited to be a bit more coherent. 

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007-2010 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,
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
26
25
 
27
26
 
28
27
# Ancestry 1:
238
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
239
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
240
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
241
 
                    't':['i', 's'], 'u':['s', 'j'],
 
240
                    't':['i', 's'], 'u':['s', 'j'], 
242
241
                    }
243
242
 
244
243
# Graph where different walkers will race to find the common and uncommon
526
525
        graph = self.make_graph(history_shortcut)
527
526
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
528
527
 
529
 
    def test_lefthand_distance_smoke(self):
530
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
531
 
        graph = self.make_graph(history_shortcut)
532
 
        distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
533
 
        self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
534
 
 
535
 
    def test_lefthand_distance_ghosts(self):
536
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
537
 
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
538
 
        graph = self.make_graph(nodes)
539
 
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
540
 
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
541
 
 
542
528
    def test_recursive_unique_lca(self):
543
529
        """Test finding a unique least common ancestor.
544
530
 
675
661
        self.assertEqual((set(['e']), set(['f', 'g'])),
676
662
                         graph.find_difference('e', 'f'))
677
663
 
678
 
 
679
664
    def test_stacked_parents_provider(self):
680
665
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
666
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
682
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
683
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
684
 
                         stacked.get_parent_map(['rev1', 'rev2']))
685
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
686
 
                         stacked.get_parent_map(['rev2', 'rev1']))
687
 
        self.assertEqual({'rev2':['rev3']},
688
 
                         stacked.get_parent_map(['rev2', 'rev2']))
689
 
        self.assertEqual({'rev1':['rev4']},
690
 
                         stacked.get_parent_map(['rev1', 'rev1']))
691
 
    
692
 
    def test_stacked_parents_provider_overlapping(self):
693
 
        # rev2 is availible in both providers.
694
 
        # 1
695
 
        # |
696
 
        # 2
697
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
699
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
700
 
        self.assertEqual({'rev2': ['rev1']},
701
 
                         stacked.get_parent_map(['rev2']))
702
 
 
703
 
    def test__stacked_parents_provider_deprecated(self):
704
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
705
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
706
 
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
707
 
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
 
667
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
708
668
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
669
                         stacked.get_parent_map(['rev1', 'rev2']))
710
670
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
738
698
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
699
        self.assertTrue('null:' not in instrumented_provider.calls)
740
700
 
741
 
    def test_is_between(self):
742
 
        graph = self.make_graph(ancestry_1)
743
 
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
744
 
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
745
 
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
746
 
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
747
 
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
748
 
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
749
 
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
750
 
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
751
 
 
752
701
    def test_is_ancestor_boundary(self):
753
702
        """Ensure that we avoid searching the whole graph.
754
 
 
 
703
        
755
704
        This requires searching through b as a common ancestor, so we
756
705
        can identify that e is common.
757
706
        """
777
726
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
778
727
        expected['g'] = None
779
728
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
780
 
        expected.pop('a')
 
729
        expected.pop('a') 
781
730
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
782
731
 
783
732
    def test_filter_candidate_lca(self):
885
834
 
886
835
    def _run_heads_break_deeper(self, graph_dict, search):
887
836
        """Run heads on a graph-as-a-dict.
888
 
 
 
837
        
889
838
        If the search asks for the parents of 'deeper' the test will fail.
890
839
        """
891
840
        class stub(object):
1032
981
        :param next: A callable to advance the search.
1033
982
        """
1034
983
        for seen, recipe, included_keys, starts, stops in instructions:
1035
 
            # Adjust for recipe contract changes that don't vary for all the
1036
 
            # current tests.
1037
 
            recipe = ('search',) + recipe
1038
984
            next()
1039
985
            if starts is not None:
1040
986
                search.start_searching(starts)
1054
1000
        search = graph._make_breadth_first_searcher(['head'])
1055
1001
        # At the start, nothing has been seen, to its all excluded:
1056
1002
        result = search.get_result()
1057
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
1003
        self.assertEqual((set(['head']), set(['head']), 0),
1058
1004
            result.get_recipe())
1059
1005
        self.assertEqual(set(), result.get_keys())
1060
1006
        self.assertEqual(set(), search.seen)
1086
1032
        search.start_searching(['head'])
1087
1033
        # head has been seen:
1088
1034
        result = search.get_result()
1089
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
1035
        self.assertEqual((set(['head']), set(['child']), 1),
1090
1036
            result.get_recipe())
1091
1037
        self.assertEqual(set(['head']), result.get_keys())
1092
1038
        self.assertEqual(set(['head']), search.seen)
1123
1069
        search = graph._make_breadth_first_searcher(['head'])
1124
1070
        expected = [
1125
1071
            # NULL_REVISION and ghost1 have not been returned
1126
 
            (set(['head']),
1127
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1072
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1128
1073
             ['head'], None, [NULL_REVISION, 'ghost1']),
1129
1074
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1130
1075
            # next iteration.
1137
1082
        search = graph._make_breadth_first_searcher(['head'])
1138
1083
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1139
1084
 
1140
 
    def test_breadth_first_stop_searching_late(self):
1141
 
        # A client should be able to say 'stop node X' and have it excluded
1142
 
        # from the result even if X was seen in an older iteration of the
1143
 
        # search.
1144
 
        graph = self.make_graph({
1145
 
            'head':['middle'],
1146
 
            'middle':['child'],
1147
 
            'child':[NULL_REVISION],
1148
 
            NULL_REVISION:[],
1149
 
            })
1150
 
        search = graph._make_breadth_first_searcher(['head'])
1151
 
        expected = [
1152
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1153
 
             ['head'], None, None),
1154
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1155
 
             ['head', 'middle'], None, None),
1156
 
            # 'middle' came from the previous iteration, but we don't stop
1157
 
            # searching it until *after* advancing the searcher.
1158
 
            (set(['head', 'middle', 'child']),
1159
 
             (set(['head']), set(['middle', 'child']), 1),
1160
 
             ['head'], None, ['middle', 'child']),
1161
 
            ]
1162
 
        self.assertSeenAndResult(expected, search, search.next)
1163
 
        # using next_with_ghosts:
1164
 
        search = graph._make_breadth_first_searcher(['head'])
1165
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1166
 
 
1167
1085
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
1086
        graph = self.make_graph({
1169
1087
            'head':['child', 'ghost'],
1246
1164
        self.assertRaises(StopIteration, search.next)
1247
1165
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
1166
        result = search.get_result()
1249
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1167
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1250
1168
            result.get_recipe())
1251
1169
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
1170
        # using next_with_ghosts:
1255
1173
        self.assertRaises(StopIteration, search.next)
1256
1174
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
1175
        result = search.get_result()
1258
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1176
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1259
1177
            result.get_recipe())
1260
1178
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1261
1179
 
1425
1343
 
1426
1344
 
1427
1345
class TestCachingParentsProvider(tests.TestCase):
1428
 
    """These tests run with:
1429
 
 
1430
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1431
 
    ghost.
1432
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1433
 
    """
1434
1346
 
1435
1347
    def setUp(self):
1436
1348
        super(TestCachingParentsProvider, self).setUp()
1455
1367
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1456
1368
        # No new calls
1457
1369
        self.assertEqual(['b'], self.inst_pp.calls)
 
1370
        self.assertEqual({'b':None}, self.caching_pp._cache)
1458
1371
 
1459
1372
    def test_get_parent_map_mixed(self):
1460
1373
        """Anything that can be returned from cache, should be"""
1472
1385
        # only present 1 time.
1473
1386
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1474
1387
 
1475
 
    def test_note_missing_key(self):
1476
 
        """After noting that a key is missing it is cached."""
1477
 
        self.caching_pp.note_missing_key('b')
1478
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1479
 
        self.assertEqual([], self.inst_pp.calls)
1480
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1481
 
 
1482
 
 
1483
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
 
    """Test the behaviour when parents are provided that were not requested."""
1485
 
 
1486
 
    def setUp(self):
1487
 
        super(TestCachingParentsProviderExtras, self).setUp()
1488
 
        class ExtraParentsProvider(object):
1489
 
 
1490
 
            def get_parent_map(self, keys):
1491
 
                return {'rev1': [], 'rev2': ['rev1',]}
1492
 
 
1493
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1494
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1495
 
            get_parent_map=self.inst_pp.get_parent_map)
1496
 
 
1497
 
    def test_uncached(self):
1498
 
        self.caching_pp.disable_cache()
1499
 
        self.assertEqual({'rev1': []},
1500
 
                         self.caching_pp.get_parent_map(['rev1']))
1501
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1502
 
        self.assertIs(None, self.caching_pp._cache)
1503
 
 
1504
 
    def test_cache_initially_empty(self):
1505
 
        self.assertEqual({}, self.caching_pp._cache)
1506
 
 
1507
 
    def test_cached(self):
1508
 
        self.assertEqual({'rev1': []},
1509
 
                         self.caching_pp.get_parent_map(['rev1']))
1510
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1511
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1512
 
                         self.caching_pp._cache)
1513
 
        self.assertEqual({'rev1': []},
1514
 
                          self.caching_pp.get_parent_map(['rev1']))
1515
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1516
 
 
1517
 
    def test_disable_cache_clears_cache(self):
1518
 
        # Put something in the cache
1519
 
        self.caching_pp.get_parent_map(['rev1'])
1520
 
        self.assertEqual(2, len(self.caching_pp._cache))
1521
 
        self.caching_pp.disable_cache()
1522
 
        self.assertIs(None, self.caching_pp._cache)
1523
 
 
1524
 
    def test_enable_cache_raises(self):
1525
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1526
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1527
 
 
1528
 
    def test_cache_misses(self):
1529
 
        self.caching_pp.get_parent_map(['rev3'])
1530
 
        self.caching_pp.get_parent_map(['rev3'])
1531
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1532
 
 
1533
 
    def test_no_cache_misses(self):
1534
 
        self.caching_pp.disable_cache()
1535
 
        self.caching_pp.enable_cache(cache_misses=False)
1536
 
        self.caching_pp.get_parent_map(['rev3'])
1537
 
        self.caching_pp.get_parent_map(['rev3'])
1538
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1539
 
 
1540
 
    def test_cache_extras(self):
1541
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1542
 
        self.assertEqual({'rev2': ['rev1']},
1543
 
                         self.caching_pp.get_parent_map(['rev2']))
1544
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1545
 
 
1546
1388
 
1547
1389
class TestCollapseLinearRegions(tests.TestCase):
1548
1390
 
1580
1422
        # 2 and 3 cannot be removed because 1 has 2 parents
1581
1423
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1582
1424
        self.assertCollapsed(d, d)
1583
 
 
1584
 
 
1585
 
class TestGraphThunkIdsToKeys(tests.TestCase):
1586
 
 
1587
 
    def test_heads(self):
1588
 
        # A
1589
 
        # |\
1590
 
        # B C
1591
 
        # |/
1592
 
        # D
1593
 
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
 
             ('B',): [('A',)], ('A',): []}
1595
 
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1597
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1598
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1599
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
 
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1601
 
 
1602
 
 
1603
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1605
 
 
1606
 
    def test_get_keys(self):
1607
 
        builder = self.make_branch_builder('b')
1608
 
        builder.start_series()
1609
 
        builder.build_snapshot('rev-1', None, [
1610
 
            ('add', ('', 'root-id', 'directory', ''))])
1611
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1612
 
        builder.finish_series()
1613
 
        repo = builder.get_branch().repository
1614
 
        repo.lock_read()
1615
 
        self.addCleanup(repo.unlock)
1616
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1617
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1618
 
 
1619
 
    def test_get_keys_excludes_ghosts(self):
1620
 
        builder = self.make_branch_builder('b')
1621
 
        builder.start_series()
1622
 
        builder.build_snapshot('rev-1', None, [
1623
 
            ('add', ('', 'root-id', 'directory', ''))])
1624
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1625
 
        builder.finish_series()
1626
 
        repo = builder.get_branch().repository
1627
 
        repo.lock_read()
1628
 
        self.addCleanup(repo.unlock)
1629
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1630
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1631
 
 
1632
 
    def test_get_keys_excludes_null(self):
1633
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1634
 
        # somewhere other than the last element, which can happen in real
1635
 
        # ancestries.
1636
 
        class StubGraph(object):
1637
 
            def iter_ancestry(self, keys):
1638
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
 
        result_keys = result._get_keys(StubGraph())
1641
 
        # Only the non-null keys from the ancestry appear.
1642
 
        self.assertEqual(set(['foo']), set(result_keys))
1643
 
 
1644
 
 
1645
 
class TestPendingAncestryResultRefine(TestGraphBase):
1646
 
 
1647
 
    def test_refine(self):
1648
 
        # Used when pulling from a stacked repository, so test some revisions
1649
 
        # being satisfied from the stacking branch.
1650
 
        g = self.make_graph(
1651
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1652
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1653
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1654
 
        result = result.refine(set(['tip']), set(['mid']))
1655
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1656
 
        result = result.refine(set(['mid', 'tag', 'base']),
1657
 
            set([NULL_REVISION]))
1658
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1659
 
        self.assertTrue(result.is_empty())
1660
 
 
1661
 
 
1662
 
class TestSearchResultRefine(TestGraphBase):
1663
 
 
1664
 
    def test_refine(self):
1665
 
        # Used when pulling from a stacked repository, so test some revisions
1666
 
        # being satisfied from the stacking branch.
1667
 
        g = self.make_graph(
1668
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1669
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1670
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1671
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1672
 
        result = result.refine(set(['tip']), set(['mid']))
1673
 
        recipe = result.get_recipe()
1674
 
        # We should be starting from tag (original head) and mid (seen ref)
1675
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1676
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1677
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1678
 
        self.assertEqual(3, recipe[3])
1679
 
        result = result.refine(set(['mid', 'tag', 'base']),
1680
 
            set([NULL_REVISION]))
1681
 
        recipe = result.get_recipe()
1682
 
        # We should be starting from nothing (NULL was known as a cut point)
1683
 
        self.assertEqual(set([]), recipe[1])
1684
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1685
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1686
 
        # define this as not including mid, for minimal results, but it is
1687
 
        # still 'correct' to include mid, and simpler/easier.
1688
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
 
        self.assertEqual(0, recipe[3])
1690
 
        self.assertTrue(result.is_empty())