424
426
def __init__(self, parents_provider):
426
428
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
433
430
def get_parent_map(self, nodes):
434
431
self.calls.extend(nodes)
435
432
return self._real_parents_provider.get_parent_map(nodes)
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)
442
class SharedInstrumentedParentsProvider(object):
444
def __init__(self, parents_provider, calls, 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
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)
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)
463
435
class TestGraphBase(tests.TestCase):
703
675
self.assertEqual((set(['e']), set(['f', 'g'])),
704
676
graph.find_difference('e', 'f'))
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']))
692
def test_stacked_parents_provider_overlapping(self):
693
# rev2 is availible in both providers.
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']))
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']))
706
717
def test_iter_topo_order(self):
707
718
graph = self.make_graph(ancestry_1)
708
719
args = ['rev2a', 'rev3', 'rev1']
1413
1424
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1416
class TestFindDescendants(TestGraphBase):
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)
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']),
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)
1434
class TestFindLefthandMerger(TestGraphBase):
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))
1440
def test_find_lefthand_merger_rev2b(self):
1441
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1443
def test_find_lefthand_merger_rev2a(self):
1444
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1446
def test_find_lefthand_merger_rev4(self):
1447
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1449
def test_find_lefthand_merger_f(self):
1450
self.check_merger('i', complex_shortcut, 'f', 'm')
1452
def test_find_lefthand_merger_g(self):
1453
self.check_merger('i', complex_shortcut, 'g', 'm')
1455
def test_find_lefthand_merger_h(self):
1456
self.check_merger('n', complex_shortcut, 'h', 'n')
1459
class TestGetChildMap(TestGraphBase):
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'],
1471
1427
class TestCachingParentsProvider(tests.TestCase):
1472
1428
"""These tests run with:
1659
1599
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1660
1600
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
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'])))
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')])
1680
1603
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1681
1604
"""Tests for bzrlib.graph.PendingAncestryResult."""
1765
1688
self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1766
1689
self.assertEqual(0, recipe[3])
1767
1690
self.assertTrue(result.is_empty())
1770
class TestSearchResultFromParentMap(TestGraphBase):
1772
def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
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))
1779
def test_no_parents(self):
1780
self.assertSearchResult([], [], 0, {})
1781
self.assertSearchResult([], [], 0, None)
1783
def test_ancestry_1(self):
1784
self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
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])
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,
1799
parent_map.update((k,extended_history_shortcut[k])
1800
for k in ['d', 'a'])
1801
self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
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])
1811
class TestLimitedSearchResultFromParentMap(TestGraphBase):
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))
1820
def test_empty_ancestry(self):
1821
self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
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)
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)
1841
class TestStackedParentsProvider(tests.TestCase):
1844
super(TestStackedParentsProvider, self).setUp()
1847
def get_shared_provider(self, info, ancestry, has_cached):
1848
pp = _mod_graph.DictParentsProvider(ancestry)
1850
pp.get_cached_parent_map = pp.get_parent_map
1851
return SharedInstrumentedParentsProvider(pp, self.calls, info)
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']))
1866
def test_stacked_parents_provider_overlapping(self):
1867
# rev2 is availible in both providers.
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']))
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',)},
1882
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
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)
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']),