← 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: 2009-03-16 08:26:29 UTC
  • mfrom: (4145.1.6 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20090316082629-xuzqut3b3ur5bn3b
(robertc) Add a new repository method refresh_data to allow clean
        handling of _real_repositories after inserting a stream via the
        smart server. (Robert Collins, Andrew Bennetts)

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:
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']},
1032
992
        :param next: A callable to advance the search.
1033
993
        """
1034
994
        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
995
            next()
1039
996
            if starts is not None:
1040
997
                search.start_searching(starts)
1054
1011
        search = graph._make_breadth_first_searcher(['head'])
1055
1012
        # At the start, nothing has been seen, to its all excluded:
1056
1013
        result = search.get_result()
1057
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
1014
        self.assertEqual((set(['head']), set(['head']), 0),
1058
1015
            result.get_recipe())
1059
1016
        self.assertEqual(set(), result.get_keys())
1060
1017
        self.assertEqual(set(), search.seen)
1086
1043
        search.start_searching(['head'])
1087
1044
        # head has been seen:
1088
1045
        result = search.get_result()
1089
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
1046
        self.assertEqual((set(['head']), set(['child']), 1),
1090
1047
            result.get_recipe())
1091
1048
        self.assertEqual(set(['head']), result.get_keys())
1092
1049
        self.assertEqual(set(['head']), search.seen)
1246
1203
        self.assertRaises(StopIteration, search.next)
1247
1204
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
1205
        result = search.get_result()
1249
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1206
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1250
1207
            result.get_recipe())
1251
1208
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
1209
        # using next_with_ghosts:
1255
1212
        self.assertRaises(StopIteration, search.next)
1256
1213
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
1214
        result = search.get_result()
1258
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
1215
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1259
1216
            result.get_recipe())
1260
1217
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1261
1218
 
1425
1382
 
1426
1383
 
1427
1384
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
1385
 
1435
1386
    def setUp(self):
1436
1387
        super(TestCachingParentsProvider, self).setUp()
1455
1406
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1456
1407
        # No new calls
1457
1408
        self.assertEqual(['b'], self.inst_pp.calls)
 
1409
        self.assertEqual({'b':None}, self.caching_pp._cache)
1458
1410
 
1459
1411
    def test_get_parent_map_mixed(self):
1460
1412
        """Anything that can be returned from cache, should be"""
1472
1424
        # only present 1 time.
1473
1425
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1474
1426
 
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
1427
 
1483
1428
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
1429
    """Test the behaviour when parents are provided that were not requested."""
1582
1527
        self.assertCollapsed(d, d)
1583
1528
 
1584
1529
 
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):
 
1530
class TestPendingAncestryResult(TestCaseWithMemoryTransport):
1604
1531
    """Tests for bzrlib.graph.PendingAncestryResult."""
1605
1532
 
1606
1533
    def test_get_keys(self):
1613
1540
        repo = builder.get_branch().repository
1614
1541
        repo.lock_read()
1615
1542
        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()))
 
1543
        par = _mod_graph.PendingAncestryResult(['rev-2'], repo)
 
1544
        self.assertEqual(set(['rev-1', 'rev-2']), set(par.get_keys()))
1631
1545
 
1632
1546
    def test_get_keys_excludes_null(self):
1633
1547
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1636
1550
        class StubGraph(object):
1637
1551
            def iter_ancestry(self, keys):
1638
1552
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
 
        result_keys = result._get_keys(StubGraph())
 
1553
        par = _mod_graph.PendingAncestryResult(['rev-3'], None)
 
1554
        par_keys = par._get_keys(StubGraph())
1641
1555
        # 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())
 
1556
        self.assertEqual(set(['foo']), set(par_keys))
 
1557