← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

add gettext to all the builtin commands outf usage

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-2011 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
17
17
from bzrlib import (
18
18
    errors,
19
19
    graph as _mod_graph,
20
 
    symbol_versioning,
21
20
    tests,
22
21
    )
23
22
from bzrlib.revision import NULL_REVISION
24
23
from bzrlib.tests import TestCaseWithMemoryTransport
25
 
from bzrlib.symbol_versioning import deprecated_in
26
24
 
27
25
 
28
26
# Ancestry 1:
426
424
    def __init__(self, parents_provider):
427
425
        self.calls = []
428
426
        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
429
432
 
430
433
    def get_parent_map(self, nodes):
431
434
        self.calls.extend(nodes)
432
435
        return self._real_parents_provider.get_parent_map(nodes)
433
436
 
 
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
 
434
462
 
435
463
class TestGraphBase(tests.TestCase):
436
464
 
675
703
        self.assertEqual((set(['e']), set(['f', 'g'])),
676
704
                         graph.find_difference('e', 'f'))
677
705
 
678
 
 
679
 
    def test_stacked_parents_provider(self):
680
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
 
        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])
708
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
 
                         stacked.get_parent_map(['rev1', 'rev2']))
710
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
711
 
                         stacked.get_parent_map(['rev2', 'rev1']))
712
 
        self.assertEqual({'rev2':['rev3']},
713
 
                         stacked.get_parent_map(['rev2', 'rev2']))
714
 
        self.assertEqual({'rev1':['rev4']},
715
 
                         stacked.get_parent_map(['rev1', 'rev1']))
716
 
 
717
706
    def test_iter_topo_order(self):
718
707
        graph = self.make_graph(ancestry_1)
719
708
        args = ['rev2a', 'rev3', 'rev1']
1424
1413
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1425
1414
 
1426
1415
 
 
1416
class TestFindDescendants(TestGraphBase):
 
1417
 
 
1418
    def test_find_descendants_rev1_rev3(self):
 
1419
        graph = self.make_graph(ancestry_1)
 
1420
        descendants = graph.find_descendants('rev1', 'rev3')
 
1421
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
 
1422
 
 
1423
    def test_find_descendants_rev1_rev4(self):
 
1424
        graph = self.make_graph(ancestry_1)
 
1425
        descendants = graph.find_descendants('rev1', 'rev4')
 
1426
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
 
1427
                         descendants)
 
1428
 
 
1429
    def test_find_descendants_rev2a_rev4(self):
 
1430
        graph = self.make_graph(ancestry_1)
 
1431
        descendants = graph.find_descendants('rev2a', 'rev4')
 
1432
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
 
1433
 
 
1434
class TestFindLefthandMerger(TestGraphBase):
 
1435
 
 
1436
    def check_merger(self, result, ancestry, merged, tip):
 
1437
        graph = self.make_graph(ancestry)
 
1438
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
 
1439
 
 
1440
    def test_find_lefthand_merger_rev2b(self):
 
1441
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
 
1442
 
 
1443
    def test_find_lefthand_merger_rev2a(self):
 
1444
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
 
1445
 
 
1446
    def test_find_lefthand_merger_rev4(self):
 
1447
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
 
1448
 
 
1449
    def test_find_lefthand_merger_f(self):
 
1450
        self.check_merger('i', complex_shortcut, 'f', 'm')
 
1451
 
 
1452
    def test_find_lefthand_merger_g(self):
 
1453
        self.check_merger('i', complex_shortcut, 'g', 'm')
 
1454
 
 
1455
    def test_find_lefthand_merger_h(self):
 
1456
        self.check_merger('n', complex_shortcut, 'h', 'n')
 
1457
 
 
1458
 
 
1459
class TestGetChildMap(TestGraphBase):
 
1460
 
 
1461
    def test_get_child_map(self):
 
1462
        graph = self.make_graph(ancestry_1)
 
1463
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
 
1464
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
 
1465
                          'rev2a': ['rev3'],
 
1466
                          'rev2b': ['rev4'],
 
1467
                          'rev3': ['rev4']},
 
1468
                          child_map)
 
1469
 
 
1470
 
1427
1471
class TestCachingParentsProvider(tests.TestCase):
1428
1472
    """These tests run with:
1429
1473
 
1434
1478
 
1435
1479
    def setUp(self):
1436
1480
        super(TestCachingParentsProvider, self).setUp()
1437
 
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
 
1481
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1438
1482
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
1483
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1440
1484
 
1479
1523
        self.assertEqual([], self.inst_pp.calls)
1480
1524
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1481
1525
 
 
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
 
1482
1534
 
1483
1535
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
1536
    """Test the behaviour when parents are provided that were not requested."""
1543
1595
                         self.caching_pp.get_parent_map(['rev2']))
1544
1596
        self.assertEqual(['rev3'], self.inst_pp.calls)
1545
1597
 
 
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
 
1546
1606
 
1547
1607
class TestCollapseLinearRegions(tests.TestCase):
1548
1608
 
1599
1659
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
1660
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1601
1661
 
 
1662
    def test_add_node(self):
 
1663
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1664
        g = _mod_graph.KnownGraph(d)
 
1665
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1666
        graph_thunk.add_node("D", ["A", "C"])
 
1667
        self.assertEqual(['B', 'D'],
 
1668
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
 
1669
 
 
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
 
1602
1679
 
1603
1680
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
1681
    """Tests for bzrlib.graph.PendingAncestryResult."""
1688
1765
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
1766
        self.assertEqual(0, recipe[3])
1690
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
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)