← 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-10-14 16:54:26 UTC
  • mfrom: (6216.1.1 remove-this-file)
  • Revision ID: pqm@pqm.ubuntu.com-20111014165426-tjix4e6idryf1r2z
(jelmer) Remove an accidentally committed .THIS file. (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
 
            state = search.get_state()
1033
 
            self.assertEqual(set(included_keys), state[2])
 
1032
            result = search.get_result()
 
1033
            self.assertEqual(recipe, result.get_recipe())
 
1034
            self.assertEqual(set(included_keys), result.get_keys())
1034
1035
            self.assertEqual(seen, search.seen)
1035
1036
 
1036
1037
    def test_breadth_first_get_result_excludes_current_pending(self):
1041
1042
            })
1042
1043
        search = graph._make_breadth_first_searcher(['head'])
1043
1044
        # At the start, nothing has been seen, to its all excluded:
1044
 
        state = search.get_state()
1045
 
        self.assertEqual((set(['head']), set(['head']), set()),
1046
 
            state)
 
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())
1047
1049
        self.assertEqual(set(), search.seen)
1048
1050
        # using next:
1049
1051
        expected = [
1072
1074
        # Starting with nothing and adding a search works:
1073
1075
        search.start_searching(['head'])
1074
1076
        # head has been seen:
1075
 
        state = search.get_state()
1076
 
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
1077
 
            state)
 
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())
1078
1081
        self.assertEqual(set(['head']), search.seen)
1079
1082
        # using next:
1080
1083
        expected = [
1231
1234
        self.assertSeenAndResult(expected, search, search.next)
1232
1235
        self.assertRaises(StopIteration, search.next)
1233
1236
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1234
 
        state = search.get_state()
1235
 
        self.assertEqual(
1236
 
            (set(['ghost', 'head']), set(['ghost']),
1237
 
                set(['head', NULL_REVISION])),
1238
 
            state)
 
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())
1239
1241
        # using next_with_ghosts:
1240
1242
        search = graph._make_breadth_first_searcher(['head'])
1241
1243
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1244
        self.assertRaises(StopIteration, search.next)
1243
1245
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1244
 
        state = search.get_state()
1245
 
        self.assertEqual(
1246
 
            (set(['ghost', 'head']), set(['ghost']),
1247
 
                set(['head', NULL_REVISION])),
1248
 
            state)
 
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())
1249
1250
 
1250
1251
 
1251
1252
class TestFindUniqueAncestors(TestGraphBase):
1676
1677
                 for n in graph_thunk.merge_sort('C')])
1677
1678
 
1678
1679
 
 
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
 
1679
1841
class TestStackedParentsProvider(tests.TestCase):
1680
1842
 
1681
1843
    def setUp(self):