← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

(gz) Fix test failure on alpha by correcting format string for
 gc_chk_sha1_record (Martin [gz])

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
21
21
    )
22
22
from bzrlib.revision import NULL_REVISION
23
23
from bzrlib.tests import TestCaseWithMemoryTransport
 
24
from bzrlib.symbol_versioning import deprecated_in
24
25
 
25
26
 
26
27
# Ancestry 1:
424
425
    def __init__(self, parents_provider):
425
426
        self.calls = []
426
427
        self._real_parents_provider = parents_provider
427
 
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
428
 
        if get_cached is not None:
429
 
            # Only expose the underlying 'get_cached_parent_map' function if
430
 
            # the wrapped provider has it.
431
 
            self.get_cached_parent_map = self._get_cached_parent_map
432
428
 
433
429
    def get_parent_map(self, nodes):
434
430
        self.calls.extend(nodes)
435
431
        return self._real_parents_provider.get_parent_map(nodes)
436
432
 
437
 
    def _get_cached_parent_map(self, nodes):
438
 
        self.calls.append(('cached', sorted(nodes)))
439
 
        return self._real_parents_provider.get_cached_parent_map(nodes)
440
 
 
441
 
 
442
 
class SharedInstrumentedParentsProvider(object):
443
 
 
444
 
    def __init__(self, parents_provider, calls, info):
445
 
        self.calls = calls
446
 
        self.info = info
447
 
        self._real_parents_provider = parents_provider
448
 
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
449
 
        if get_cached is not None:
450
 
            # Only expose the underlying 'get_cached_parent_map' function if
451
 
            # the wrapped provider has it.
452
 
            self.get_cached_parent_map = self._get_cached_parent_map
453
 
 
454
 
    def get_parent_map(self, nodes):
455
 
        self.calls.append((self.info, sorted(nodes)))
456
 
        return self._real_parents_provider.get_parent_map(nodes)
457
 
 
458
 
    def _get_cached_parent_map(self, nodes):
459
 
        self.calls.append((self.info, 'cached', sorted(nodes)))
460
 
        return self._real_parents_provider.get_cached_parent_map(nodes)
461
 
 
462
433
 
463
434
class TestGraphBase(tests.TestCase):
464
435
 
703
674
        self.assertEqual((set(['e']), set(['f', 'g'])),
704
675
                         graph.find_difference('e', 'f'))
705
676
 
 
677
 
 
678
    def test_stacked_parents_provider(self):
 
679
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
680
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
681
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
682
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
683
                         stacked.get_parent_map(['rev1', 'rev2']))
 
684
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
685
                         stacked.get_parent_map(['rev2', 'rev1']))
 
686
        self.assertEqual({'rev2':['rev3']},
 
687
                         stacked.get_parent_map(['rev2', 'rev2']))
 
688
        self.assertEqual({'rev1':['rev4']},
 
689
                         stacked.get_parent_map(['rev1', 'rev1']))
 
690
    
 
691
    def test_stacked_parents_provider_overlapping(self):
 
692
        # rev2 is availible in both providers.
 
693
        # 1
 
694
        # |
 
695
        # 2
 
696
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
697
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
698
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
699
        self.assertEqual({'rev2': ['rev1']},
 
700
                         stacked.get_parent_map(['rev2']))
 
701
 
706
702
    def test_iter_topo_order(self):
707
703
        graph = self.make_graph(ancestry_1)
708
704
        args = ['rev2a', 'rev3', 'rev1']
1478
1474
 
1479
1475
    def setUp(self):
1480
1476
        super(TestCachingParentsProvider, self).setUp()
1481
 
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
 
1477
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1482
1478
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1483
1479
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1484
1480
 
1523
1519
        self.assertEqual([], self.inst_pp.calls)
1524
1520
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1525
1521
 
1526
 
    def test_get_cached_parent_map(self):
1527
 
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1528
 
        self.assertEqual([], self.inst_pp.calls)
1529
 
        self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1530
 
        self.assertEqual(['a'], self.inst_pp.calls)
1531
 
        self.assertEqual({'a': ('b',)},
1532
 
                         self.caching_pp.get_cached_parent_map(['a']))
1533
 
 
1534
1522
 
1535
1523
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1536
1524
    """Test the behaviour when parents are provided that were not requested."""
1595
1583
                         self.caching_pp.get_parent_map(['rev2']))
1596
1584
        self.assertEqual(['rev3'], self.inst_pp.calls)
1597
1585
 
1598
 
    def test_extras_using_cached(self):
1599
 
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1600
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1601
 
        self.assertEqual({'rev2': ['rev1']},
1602
 
                         self.caching_pp.get_cached_parent_map(['rev2']))
1603
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1604
 
 
1605
 
 
1606
1586
 
1607
1587
class TestCollapseLinearRegions(tests.TestCase):
1608
1588
 
1667
1647
        self.assertEqual(['B', 'D'],
1668
1648
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
1669
1649
 
1670
 
    def test_merge_sort(self):
1671
 
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1672
 
        g = _mod_graph.KnownGraph(d)
1673
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1674
 
        graph_thunk.add_node("D", ["A", "C"])
1675
 
        self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1676
 
            [(n.key, n.merge_depth, n.revno, n.end_of_merge)
1677
 
                 for n in graph_thunk.merge_sort('C')])
1678
 
 
1679
1650
 
1680
1651
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1681
1652
    """Tests for bzrlib.graph.PendingAncestryResult."""
1765
1736
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1766
1737
        self.assertEqual(0, recipe[3])
1767
1738
        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
 
class TestStackedParentsProvider(tests.TestCase):
1842
 
 
1843
 
    def setUp(self):
1844
 
        super(TestStackedParentsProvider, self).setUp()
1845
 
        self.calls = []
1846
 
 
1847
 
    def get_shared_provider(self, info, ancestry, has_cached):
1848
 
        pp = _mod_graph.DictParentsProvider(ancestry)
1849
 
        if has_cached:
1850
 
            pp.get_cached_parent_map = pp.get_parent_map
1851
 
        return SharedInstrumentedParentsProvider(pp, self.calls, info)
1852
 
 
1853
 
    def test_stacked_parents_provider(self):
1854
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1855
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1856
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1857
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1858
 
                         stacked.get_parent_map(['rev1', 'rev2']))
1859
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1860
 
                         stacked.get_parent_map(['rev2', 'rev1']))
1861
 
        self.assertEqual({'rev2':['rev3']},
1862
 
                         stacked.get_parent_map(['rev2', 'rev2']))
1863
 
        self.assertEqual({'rev1':['rev4']},
1864
 
                         stacked.get_parent_map(['rev1', 'rev1']))
1865
 
 
1866
 
    def test_stacked_parents_provider_overlapping(self):
1867
 
        # rev2 is availible in both providers.
1868
 
        # 1
1869
 
        # |
1870
 
        # 2
1871
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1872
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1873
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1874
 
        self.assertEqual({'rev2': ['rev1']},
1875
 
                         stacked.get_parent_map(['rev2']))
1876
 
 
1877
 
    def test_handles_no_get_cached_parent_map(self):
1878
 
        # this shows that we both handle when a provider doesn't implement
1879
 
        # get_cached_parent_map
1880
 
        pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1881
 
                                       has_cached=False)
1882
 
        pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1883
 
                                       has_cached=True)
1884
 
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1885
 
        self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1886
 
        # No call on 'pp1' because it doesn't provide get_cached_parent_map
1887
 
        self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1888
 
 
1889
 
    def test_query_order(self):
1890
 
        # We should call get_cached_parent_map on all providers before we call
1891
 
        # get_parent_map. Further, we should track what entries we have found,
1892
 
        # and not re-try them.
1893
 
        pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1894
 
        pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1895
 
        pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1896
 
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1897
 
        self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1898
 
                         stacked.get_parent_map(['a', 'b', 'c', 'd']))
1899
 
        self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1900
 
                          # No call to pp2, because it doesn't have cached
1901
 
                          ('pp3', 'cached', ['b', 'c', 'd']),
1902
 
                          ('pp1', ['c', 'd']),
1903
 
                          ('pp2', ['c', 'd']),
1904
 
                          ('pp3', ['d']),
1905
 
                         ], self.calls)