← 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: Patch Queue Manager
  • Date: 2011-12-06 16:05:01 UTC
  • mfrom: (6341.1.6 vf-search)
  • Revision ID: pqm@pqm.ubuntu.com-20111206160501-uxh307vklxc6zztm
(jelmer) Move search result handling into a separate module. (Jelmer
 Vernooij)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1029
1029
                search.start_searching(starts)
1030
1030
            if stops is not None:
1031
1031
                search.stop_searching_any(stops)
1032
 
            result = search.get_result()
1033
 
            self.assertEqual(recipe, result.get_recipe())
1034
 
            self.assertEqual(set(included_keys), result.get_keys())
 
1032
            state = search.get_state()
 
1033
            self.assertEqual(set(included_keys), state[2])
1035
1034
            self.assertEqual(seen, search.seen)
1036
1035
 
1037
1036
    def test_breadth_first_get_result_excludes_current_pending(self):
1042
1041
            })
1043
1042
        search = graph._make_breadth_first_searcher(['head'])
1044
1043
        # At the start, nothing has been seen, to its all excluded:
1045
 
        result = search.get_result()
1046
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
1047
 
            result.get_recipe())
1048
 
        self.assertEqual(set(), result.get_keys())
 
1044
        state = search.get_state()
 
1045
        self.assertEqual((set(['head']), set(['head']), set()),
 
1046
            state)
1049
1047
        self.assertEqual(set(), search.seen)
1050
1048
        # using next:
1051
1049
        expected = [
1074
1072
        # Starting with nothing and adding a search works:
1075
1073
        search.start_searching(['head'])
1076
1074
        # head has been seen:
1077
 
        result = search.get_result()
1078
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
1079
 
            result.get_recipe())
1080
 
        self.assertEqual(set(['head']), result.get_keys())
 
1075
        state = search.get_state()
 
1076
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
 
1077
            state)
1081
1078
        self.assertEqual(set(['head']), search.seen)
1082
1079
        # using next:
1083
1080
        expected = [
1234
1231
        self.assertSeenAndResult(expected, search, search.next)
1235
1232
        self.assertRaises(StopIteration, search.next)
1236
1233
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1237
 
        result = search.get_result()
1238
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1239
 
            result.get_recipe())
1240
 
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
1234
        state = search.get_state()
 
1235
        self.assertEqual(
 
1236
            (set(['ghost', 'head']), set(['ghost']),
 
1237
                set(['head', NULL_REVISION])),
 
1238
            state)
1241
1239
        # using next_with_ghosts:
1242
1240
        search = graph._make_breadth_first_searcher(['head'])
1243
1241
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1244
1242
        self.assertRaises(StopIteration, search.next)
1245
1243
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1246
 
        result = search.get_result()
1247
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1248
 
            result.get_recipe())
1249
 
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
1244
        state = search.get_state()
 
1245
        self.assertEqual(
 
1246
            (set(['ghost', 'head']), set(['ghost']),
 
1247
                set(['head', NULL_REVISION])),
 
1248
            state)
1250
1249
 
1251
1250
 
1252
1251
class TestFindUniqueAncestors(TestGraphBase):
1677
1676
                 for n in graph_thunk.merge_sort('C')])
1678
1677
 
1679
1678
 
1680
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1681
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1682
 
 
1683
 
    def test_get_keys(self):
1684
 
        builder = self.make_branch_builder('b')
1685
 
        builder.start_series()
1686
 
        builder.build_snapshot('rev-1', None, [
1687
 
            ('add', ('', 'root-id', 'directory', ''))])
1688
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1689
 
        builder.finish_series()
1690
 
        repo = builder.get_branch().repository
1691
 
        repo.lock_read()
1692
 
        self.addCleanup(repo.unlock)
1693
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1694
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1695
 
 
1696
 
    def test_get_keys_excludes_ghosts(self):
1697
 
        builder = self.make_branch_builder('b')
1698
 
        builder.start_series()
1699
 
        builder.build_snapshot('rev-1', None, [
1700
 
            ('add', ('', 'root-id', 'directory', ''))])
1701
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1702
 
        builder.finish_series()
1703
 
        repo = builder.get_branch().repository
1704
 
        repo.lock_read()
1705
 
        self.addCleanup(repo.unlock)
1706
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1707
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1708
 
 
1709
 
    def test_get_keys_excludes_null(self):
1710
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1711
 
        # somewhere other than the last element, which can happen in real
1712
 
        # ancestries.
1713
 
        class StubGraph(object):
1714
 
            def iter_ancestry(self, keys):
1715
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1716
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1717
 
        result_keys = result._get_keys(StubGraph())
1718
 
        # Only the non-null keys from the ancestry appear.
1719
 
        self.assertEqual(set(['foo']), set(result_keys))
1720
 
 
1721
 
 
1722
 
class TestPendingAncestryResultRefine(TestGraphBase):
1723
 
 
1724
 
    def test_refine(self):
1725
 
        # Used when pulling from a stacked repository, so test some revisions
1726
 
        # being satisfied from the stacking branch.
1727
 
        g = self.make_graph(
1728
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1729
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1730
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1731
 
        result = result.refine(set(['tip']), set(['mid']))
1732
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1733
 
        result = result.refine(set(['mid', 'tag', 'base']),
1734
 
            set([NULL_REVISION]))
1735
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1736
 
        self.assertTrue(result.is_empty())
1737
 
 
1738
 
 
1739
 
class TestSearchResultRefine(TestGraphBase):
1740
 
 
1741
 
    def test_refine(self):
1742
 
        # Used when pulling from a stacked repository, so test some revisions
1743
 
        # being satisfied from the stacking branch.
1744
 
        g = self.make_graph(
1745
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1746
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1747
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1748
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1749
 
        result = result.refine(set(['tip']), set(['mid']))
1750
 
        recipe = result.get_recipe()
1751
 
        # We should be starting from tag (original head) and mid (seen ref)
1752
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1753
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1754
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1755
 
        self.assertEqual(3, recipe[3])
1756
 
        result = result.refine(set(['mid', 'tag', 'base']),
1757
 
            set([NULL_REVISION]))
1758
 
        recipe = result.get_recipe()
1759
 
        # We should be starting from nothing (NULL was known as a cut point)
1760
 
        self.assertEqual(set([]), recipe[1])
1761
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1762
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1763
 
        # define this as not including mid, for minimal results, but it is
1764
 
        # still 'correct' to include mid, and simpler/easier.
1765
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1766
 
        self.assertEqual(0, recipe[3])
1767
 
        self.assertTrue(result.is_empty())
1768
 
 
1769
 
 
1770
 
class TestSearchResultFromParentMap(TestGraphBase):
1771
 
 
1772
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1773
 
                           missing_keys=()):
1774
 
        (start, stop, count) = _mod_graph.search_result_from_parent_map(
1775
 
            parent_map, missing_keys)
1776
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1777
 
                         (sorted(start), sorted(stop), count))
1778
 
 
1779
 
    def test_no_parents(self):
1780
 
        self.assertSearchResult([], [], 0, {})
1781
 
        self.assertSearchResult([], [], 0, None)
1782
 
 
1783
 
    def test_ancestry_1(self):
1784
 
        self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
1785
 
                                ancestry_1)
1786
 
 
1787
 
    def test_ancestry_2(self):
1788
 
        self.assertSearchResult(['rev1b', 'rev4a'], [NULL_REVISION],
1789
 
                                len(ancestry_2), ancestry_2)
1790
 
        self.assertSearchResult(['rev1b', 'rev4a'], [],
1791
 
                                len(ancestry_2)+1, ancestry_2,
1792
 
                                missing_keys=[NULL_REVISION])
1793
 
 
1794
 
    def test_partial_search(self):
1795
 
        parent_map = dict((k,extended_history_shortcut[k])
1796
 
                          for k in ['e', 'f'])
1797
 
        self.assertSearchResult(['e', 'f'], ['d', 'a'], 2,
1798
 
                                parent_map)
1799
 
        parent_map.update((k,extended_history_shortcut[k])
1800
 
                          for k in ['d', 'a'])
1801
 
        self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
1802
 
                                parent_map)
1803
 
        parent_map['c'] = extended_history_shortcut['c']
1804
 
        self.assertSearchResult(['e', 'f'], ['b'], 6,
1805
 
                                parent_map, missing_keys=[NULL_REVISION])
1806
 
        parent_map['b'] = extended_history_shortcut['b']
1807
 
        self.assertSearchResult(['e', 'f'], [], 7,
1808
 
                                parent_map, missing_keys=[NULL_REVISION])
1809
 
 
1810
 
 
1811
 
class TestLimitedSearchResultFromParentMap(TestGraphBase):
1812
 
 
1813
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1814
 
                           missing_keys, tip_keys, depth):
1815
 
        (start, stop, count) = _mod_graph.limited_search_result_from_parent_map(
1816
 
            parent_map, missing_keys, tip_keys, depth)
1817
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1818
 
                         (sorted(start), sorted(stop), count))
1819
 
 
1820
 
    def test_empty_ancestry(self):
1821
 
        self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
1822
 
 
1823
 
    def test_ancestry_1(self):
1824
 
        self.assertSearchResult(['rev4'], ['rev1'], 4,
1825
 
                                ancestry_1, (), ['rev1'], 10)
1826
 
        self.assertSearchResult(['rev2a', 'rev2b'], ['rev1'], 2,
1827
 
                                ancestry_1, (), ['rev1'], 1)
1828
 
 
1829
 
 
1830
 
    def test_multiple_heads(self):
1831
 
        self.assertSearchResult(['e', 'f'], ['a'], 5,
1832
 
                                extended_history_shortcut, (), ['a'], 10)
1833
 
        # Note that even though we only take 1 step back, we find 'f', which
1834
 
        # means the described search will still find d and c.
1835
 
        self.assertSearchResult(['f'], ['a'], 4,
1836
 
                                extended_history_shortcut, (), ['a'], 1)
1837
 
        self.assertSearchResult(['f'], ['a'], 4,
1838
 
                                extended_history_shortcut, (), ['a'], 2)
1839
 
 
1840
 
 
1841
1679
class TestStackedParentsProvider(tests.TestCase):
1842
1680
 
1843
1681
    def setUp(self):