← 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: Martin Pool
  • Date: 2009-07-27 06:28:35 UTC
  • mto: This revision was merged to the branch mainline in revision 4587.
  • Revision ID: mbp@sourcefrog.net-20090727062835-o66p8it658tq1sma
Add CountedLock.get_physical_lock_status

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
661
662
        self.assertEqual((set(['e']), set(['f', 'g'])),
662
663
                         graph.find_difference('e', 'f'))
663
664
 
 
665
 
664
666
    def test_stacked_parents_provider(self):
665
667
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
666
668
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
667
 
        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])
668
695
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
669
696
                         stacked.get_parent_map(['rev1', 'rev2']))
670
697
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
711
738
 
712
739
    def test_is_ancestor_boundary(self):
713
740
        """Ensure that we avoid searching the whole graph.
714
 
        
 
741
 
715
742
        This requires searching through b as a common ancestor, so we
716
743
        can identify that e is common.
717
744
        """
737
764
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
738
765
        expected['g'] = None
739
766
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
740
 
        expected.pop('a') 
 
767
        expected.pop('a')
741
768
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
742
769
 
743
770
    def test_filter_candidate_lca(self):
845
872
 
846
873
    def _run_heads_break_deeper(self, graph_dict, search):
847
874
        """Run heads on a graph-as-a-dict.
848
 
        
 
875
 
849
876
        If the search asks for the parents of 'deeper' the test will fail.
850
877
        """
851
878
        class stub(object):
992
1019
        :param next: A callable to advance the search.
993
1020
        """
994
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
995
1025
            next()
996
1026
            if starts is not None:
997
1027
                search.start_searching(starts)
1011
1041
        search = graph._make_breadth_first_searcher(['head'])
1012
1042
        # At the start, nothing has been seen, to its all excluded:
1013
1043
        result = search.get_result()
1014
 
        self.assertEqual((set(['head']), set(['head']), 0),
 
1044
        self.assertEqual(('search', set(['head']), set(['head']), 0),
1015
1045
            result.get_recipe())
1016
1046
        self.assertEqual(set(), result.get_keys())
1017
1047
        self.assertEqual(set(), search.seen)
1043
1073
        search.start_searching(['head'])
1044
1074
        # head has been seen:
1045
1075
        result = search.get_result()
1046
 
        self.assertEqual((set(['head']), set(['child']), 1),
 
1076
        self.assertEqual(('search', set(['head']), set(['child']), 1),
1047
1077
            result.get_recipe())
1048
1078
        self.assertEqual(set(['head']), result.get_keys())
1049
1079
        self.assertEqual(set(['head']), search.seen)
1080
1110
        search = graph._make_breadth_first_searcher(['head'])
1081
1111
        expected = [
1082
1112
            # NULL_REVISION and ghost1 have not been returned
1083
 
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
 
1113
            (set(['head']),
 
1114
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1084
1115
             ['head'], None, [NULL_REVISION, 'ghost1']),
1085
1116
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1086
1117
            # next iteration.
1202
1233
        self.assertRaises(StopIteration, search.next)
1203
1234
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1204
1235
        result = search.get_result()
1205
 
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1236
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1206
1237
            result.get_recipe())
1207
1238
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1208
1239
        # using next_with_ghosts:
1211
1242
        self.assertRaises(StopIteration, search.next)
1212
1243
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1213
1244
        result = search.get_result()
1214
 
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1245
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1215
1246
            result.get_recipe())
1216
1247
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1217
1248
 
1381
1412
 
1382
1413
 
1383
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
    """
1384
1421
 
1385
1422
    def setUp(self):
1386
1423
        super(TestCachingParentsProvider, self).setUp()
1405
1442
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1406
1443
        # No new calls
1407
1444
        self.assertEqual(['b'], self.inst_pp.calls)
1408
 
        self.assertEqual({'b':None}, self.caching_pp._cache)
1409
1445
 
1410
1446
    def test_get_parent_map_mixed(self):
1411
1447
        """Anything that can be returned from cache, should be"""
1423
1459
        # only present 1 time.
1424
1460
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1425
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
 
1426
1469
 
1427
1470
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1428
1471
    """Test the behaviour when parents are provided that were not requested."""
1524
1567
        # 2 and 3 cannot be removed because 1 has 2 parents
1525
1568
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1526
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())