← 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: Vincent Ladeuil
  • Date: 2017-01-17 13:48:10 UTC
  • mfrom: (6615.3.6 merges)
  • mto: This revision was merged to the branch mainline in revision 6620.
  • Revision ID: v.ladeuil+lp@free.fr-20170117134810-j9p3lidfy6pfyfsc
Merge 2.7, resolving conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007, 2008, 2009 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
 
526
554
        graph = self.make_graph(history_shortcut)
527
555
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
528
556
 
 
557
    def test_lefthand_distance_smoke(self):
 
558
        """A simple does it work test for graph.lefthand_distance(keys)."""
 
559
        graph = self.make_graph(history_shortcut)
 
560
        distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
 
561
        self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
 
562
 
 
563
    def test_lefthand_distance_ghosts(self):
 
564
        """A simple does it work test for graph.lefthand_distance(keys)."""
 
565
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
 
566
        graph = self.make_graph(nodes)
 
567
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
 
568
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
 
569
 
529
570
    def test_recursive_unique_lca(self):
530
571
        """Test finding a unique least common ancestor.
531
572
 
662
703
        self.assertEqual((set(['e']), set(['f', 'g'])),
663
704
                         graph.find_difference('e', 'f'))
664
705
 
665
 
 
666
 
    def test_stacked_parents_provider(self):
667
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
668
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
669
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
670
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
671
 
                         stacked.get_parent_map(['rev1', 'rev2']))
672
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
673
 
                         stacked.get_parent_map(['rev2', 'rev1']))
674
 
        self.assertEqual({'rev2':['rev3']},
675
 
                         stacked.get_parent_map(['rev2', 'rev2']))
676
 
        self.assertEqual({'rev1':['rev4']},
677
 
                         stacked.get_parent_map(['rev1', 'rev1']))
678
 
    
679
 
    def test_stacked_parents_provider_overlapping(self):
680
 
        # rev2 is availible in both providers.
681
 
        # 1
682
 
        # |
683
 
        # 2
684
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
685
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
686
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
687
 
        self.assertEqual({'rev2': ['rev1']},
688
 
                         stacked.get_parent_map(['rev2']))
689
 
 
690
 
    def test__stacked_parents_provider_deprecated(self):
691
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
692
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
693
 
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
694
 
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
695
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
696
 
                         stacked.get_parent_map(['rev1', 'rev2']))
697
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
698
 
                         stacked.get_parent_map(['rev2', 'rev1']))
699
 
        self.assertEqual({'rev2':['rev3']},
700
 
                         stacked.get_parent_map(['rev2', 'rev2']))
701
 
        self.assertEqual({'rev1':['rev4']},
702
 
                         stacked.get_parent_map(['rev1', 'rev1']))
703
 
 
704
706
    def test_iter_topo_order(self):
705
707
        graph = self.make_graph(ancestry_1)
706
708
        args = ['rev2a', 'rev3', 'rev1']
1027
1029
                search.start_searching(starts)
1028
1030
            if stops is not None:
1029
1031
                search.stop_searching_any(stops)
1030
 
            result = search.get_result()
1031
 
            self.assertEqual(recipe, result.get_recipe())
1032
 
            self.assertEqual(set(included_keys), result.get_keys())
 
1032
            state = search.get_state()
 
1033
            self.assertEqual(set(included_keys), state[2])
1033
1034
            self.assertEqual(seen, search.seen)
1034
1035
 
1035
1036
    def test_breadth_first_get_result_excludes_current_pending(self):
1040
1041
            })
1041
1042
        search = graph._make_breadth_first_searcher(['head'])
1042
1043
        # At the start, nothing has been seen, to its all excluded:
1043
 
        result = search.get_result()
1044
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
1045
 
            result.get_recipe())
1046
 
        self.assertEqual(set(), result.get_keys())
 
1044
        state = search.get_state()
 
1045
        self.assertEqual((set(['head']), set(['head']), set()),
 
1046
            state)
1047
1047
        self.assertEqual(set(), search.seen)
1048
1048
        # using next:
1049
1049
        expected = [
1072
1072
        # Starting with nothing and adding a search works:
1073
1073
        search.start_searching(['head'])
1074
1074
        # head has been seen:
1075
 
        result = search.get_result()
1076
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
1077
 
            result.get_recipe())
1078
 
        self.assertEqual(set(['head']), result.get_keys())
 
1075
        state = search.get_state()
 
1076
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
 
1077
            state)
1079
1078
        self.assertEqual(set(['head']), search.seen)
1080
1079
        # using next:
1081
1080
        expected = [
1232
1231
        self.assertSeenAndResult(expected, search, search.next)
1233
1232
        self.assertRaises(StopIteration, search.next)
1234
1233
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1235
 
        result = search.get_result()
1236
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1237
 
            result.get_recipe())
1238
 
        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)
1239
1239
        # using next_with_ghosts:
1240
1240
        search = graph._make_breadth_first_searcher(['head'])
1241
1241
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1242
        self.assertRaises(StopIteration, search.next)
1243
1243
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1244
 
        result = search.get_result()
1245
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1246
 
            result.get_recipe())
1247
 
        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)
1248
1249
 
1249
1250
 
1250
1251
class TestFindUniqueAncestors(TestGraphBase):
1411
1412
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1412
1413
 
1413
1414
 
 
1415
class TestFindDescendants(TestGraphBase):
 
1416
 
 
1417
    def test_find_descendants_rev1_rev3(self):
 
1418
        graph = self.make_graph(ancestry_1)
 
1419
        descendants = graph.find_descendants('rev1', 'rev3')
 
1420
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
 
1421
 
 
1422
    def test_find_descendants_rev1_rev4(self):
 
1423
        graph = self.make_graph(ancestry_1)
 
1424
        descendants = graph.find_descendants('rev1', 'rev4')
 
1425
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
 
1426
                         descendants)
 
1427
 
 
1428
    def test_find_descendants_rev2a_rev4(self):
 
1429
        graph = self.make_graph(ancestry_1)
 
1430
        descendants = graph.find_descendants('rev2a', 'rev4')
 
1431
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
 
1432
 
 
1433
class TestFindLefthandMerger(TestGraphBase):
 
1434
 
 
1435
    def check_merger(self, result, ancestry, merged, tip):
 
1436
        graph = self.make_graph(ancestry)
 
1437
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
 
1438
 
 
1439
    def test_find_lefthand_merger_rev2b(self):
 
1440
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
 
1441
 
 
1442
    def test_find_lefthand_merger_rev2a(self):
 
1443
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
 
1444
 
 
1445
    def test_find_lefthand_merger_rev4(self):
 
1446
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
 
1447
 
 
1448
    def test_find_lefthand_merger_f(self):
 
1449
        self.check_merger('i', complex_shortcut, 'f', 'm')
 
1450
 
 
1451
    def test_find_lefthand_merger_g(self):
 
1452
        self.check_merger('i', complex_shortcut, 'g', 'm')
 
1453
 
 
1454
    def test_find_lefthand_merger_h(self):
 
1455
        self.check_merger('n', complex_shortcut, 'h', 'n')
 
1456
 
 
1457
 
 
1458
class TestGetChildMap(TestGraphBase):
 
1459
 
 
1460
    def test_get_child_map(self):
 
1461
        graph = self.make_graph(ancestry_1)
 
1462
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
 
1463
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
 
1464
                          'rev2a': ['rev3'],
 
1465
                          'rev2b': ['rev4'],
 
1466
                          'rev3': ['rev4']},
 
1467
                          child_map)
 
1468
 
 
1469
 
1414
1470
class TestCachingParentsProvider(tests.TestCase):
1415
1471
    """These tests run with:
1416
1472
 
1421
1477
 
1422
1478
    def setUp(self):
1423
1479
        super(TestCachingParentsProvider, self).setUp()
1424
 
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
 
1480
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1425
1481
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1426
1482
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1427
1483
 
1466
1522
        self.assertEqual([], self.inst_pp.calls)
1467
1523
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1468
1524
 
 
1525
    def test_get_cached_parent_map(self):
 
1526
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
 
1527
        self.assertEqual([], self.inst_pp.calls)
 
1528
        self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
 
1529
        self.assertEqual(['a'], self.inst_pp.calls)
 
1530
        self.assertEqual({'a': ('b',)},
 
1531
                         self.caching_pp.get_cached_parent_map(['a']))
 
1532
 
1469
1533
 
1470
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1471
1535
    """Test the behaviour when parents are provided that were not requested."""
1530
1594
                         self.caching_pp.get_parent_map(['rev2']))
1531
1595
        self.assertEqual(['rev3'], self.inst_pp.calls)
1532
1596
 
 
1597
    def test_extras_using_cached(self):
 
1598
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
 
1599
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
 
1600
        self.assertEqual({'rev2': ['rev1']},
 
1601
                         self.caching_pp.get_cached_parent_map(['rev2']))
 
1602
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1603
 
 
1604
 
1533
1605
 
1534
1606
class TestCollapseLinearRegions(tests.TestCase):
1535
1607
 
1569
1641
        self.assertCollapsed(d, d)
1570
1642
 
1571
1643
 
1572
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1573
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1574
 
 
1575
 
    def test_get_keys(self):
1576
 
        builder = self.make_branch_builder('b')
1577
 
        builder.start_series()
1578
 
        builder.build_snapshot('rev-1', None, [
1579
 
            ('add', ('', 'root-id', 'directory', ''))])
1580
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1581
 
        builder.finish_series()
1582
 
        repo = builder.get_branch().repository
1583
 
        repo.lock_read()
1584
 
        self.addCleanup(repo.unlock)
1585
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1586
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1587
 
 
1588
 
    def test_get_keys_excludes_ghosts(self):
1589
 
        builder = self.make_branch_builder('b')
1590
 
        builder.start_series()
1591
 
        builder.build_snapshot('rev-1', None, [
1592
 
            ('add', ('', 'root-id', 'directory', ''))])
1593
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1594
 
        builder.finish_series()
1595
 
        repo = builder.get_branch().repository
1596
 
        repo.lock_read()
1597
 
        self.addCleanup(repo.unlock)
1598
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1599
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1600
 
 
1601
 
    def test_get_keys_excludes_null(self):
1602
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1603
 
        # somewhere other than the last element, which can happen in real
1604
 
        # ancestries.
1605
 
        class StubGraph(object):
1606
 
            def iter_ancestry(self, keys):
1607
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1608
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1609
 
        result_keys = result._get_keys(StubGraph())
1610
 
        # Only the non-null keys from the ancestry appear.
1611
 
        self.assertEqual(set(['foo']), set(result_keys))
1612
 
 
1613
 
 
1614
 
class TestPendingAncestryResultRefine(TestGraphBase):
1615
 
 
1616
 
    def test_refine(self):
1617
 
        # Used when pulling from a stacked repository, so test some revisions
1618
 
        # being satisfied from the stacking branch.
1619
 
        g = self.make_graph(
1620
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1621
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1622
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1623
 
        result = result.refine(set(['tip']), set(['mid']))
1624
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1625
 
        result = result.refine(set(['mid', 'tag', 'base']),
1626
 
            set([NULL_REVISION]))
1627
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1628
 
        self.assertTrue(result.is_empty())
1629
 
 
1630
 
 
1631
 
class TestSearchResultRefine(TestGraphBase):
1632
 
 
1633
 
    def test_refine(self):
1634
 
        # Used when pulling from a stacked repository, so test some revisions
1635
 
        # being satisfied from the stacking branch.
1636
 
        g = self.make_graph(
1637
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1638
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1639
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1640
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1641
 
        result = result.refine(set(['tip']), set(['mid']))
1642
 
        recipe = result.get_recipe()
1643
 
        # We should be starting from tag (original head) and mid (seen ref)
1644
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1645
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1646
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1647
 
        self.assertEqual(3, recipe[3])
1648
 
        result = result.refine(set(['mid', 'tag', 'base']),
1649
 
            set([NULL_REVISION]))
1650
 
        recipe = result.get_recipe()
1651
 
        # We should be starting from nothing (NULL was known as a cut point)
1652
 
        self.assertEqual(set([]), recipe[1])
1653
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1654
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1655
 
        # define this as not including mid, for minimal results, but it is
1656
 
        # still 'correct' to include mid, and simpler/easier.
1657
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1658
 
        self.assertEqual(0, recipe[3])
1659
 
        self.assertTrue(result.is_empty())
 
1644
class TestGraphThunkIdsToKeys(tests.TestCase):
 
1645
 
 
1646
    def test_heads(self):
 
1647
        # A
 
1648
        # |\
 
1649
        # B C
 
1650
        # |/
 
1651
        # D
 
1652
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
 
1653
             ('B',): [('A',)], ('A',): []}
 
1654
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
 
1655
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1656
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
 
1657
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
 
1658
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
 
1659
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
 
1660
 
 
1661
    def test_add_node(self):
 
1662
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1663
        g = _mod_graph.KnownGraph(d)
 
1664
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1665
        graph_thunk.add_node("D", ["A", "C"])
 
1666
        self.assertEqual(['B', 'D'],
 
1667
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
 
1668
 
 
1669
    def test_merge_sort(self):
 
1670
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1671
        g = _mod_graph.KnownGraph(d)
 
1672
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
 
1673
        graph_thunk.add_node("D", ["A", "C"])
 
1674
        self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
 
1675
            [(n.key, n.merge_depth, n.revno, n.end_of_merge)
 
1676
                 for n in graph_thunk.merge_sort('C')])
 
1677
 
 
1678
 
 
1679
class TestStackedParentsProvider(tests.TestCase):
 
1680
 
 
1681
    def setUp(self):
 
1682
        super(TestStackedParentsProvider, self).setUp()
 
1683
        self.calls = []
 
1684
 
 
1685
    def get_shared_provider(self, info, ancestry, has_cached):
 
1686
        pp = _mod_graph.DictParentsProvider(ancestry)
 
1687
        if has_cached:
 
1688
            pp.get_cached_parent_map = pp.get_parent_map
 
1689
        return SharedInstrumentedParentsProvider(pp, self.calls, info)
 
1690
 
 
1691
    def test_stacked_parents_provider(self):
 
1692
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
1693
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
1694
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
1695
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
1696
                         stacked.get_parent_map(['rev1', 'rev2']))
 
1697
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
1698
                         stacked.get_parent_map(['rev2', 'rev1']))
 
1699
        self.assertEqual({'rev2':['rev3']},
 
1700
                         stacked.get_parent_map(['rev2', 'rev2']))
 
1701
        self.assertEqual({'rev1':['rev4']},
 
1702
                         stacked.get_parent_map(['rev1', 'rev1']))
 
1703
 
 
1704
    def test_stacked_parents_provider_overlapping(self):
 
1705
        # rev2 is availible in both providers.
 
1706
        # 1
 
1707
        # |
 
1708
        # 2
 
1709
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
1710
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
1711
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
1712
        self.assertEqual({'rev2': ['rev1']},
 
1713
                         stacked.get_parent_map(['rev2']))
 
1714
 
 
1715
    def test_handles_no_get_cached_parent_map(self):
 
1716
        # this shows that we both handle when a provider doesn't implement
 
1717
        # get_cached_parent_map
 
1718
        pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
 
1719
                                       has_cached=False)
 
1720
        pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
 
1721
                                       has_cached=True)
 
1722
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
 
1723
        self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
 
1724
        # No call on 'pp1' because it doesn't provide get_cached_parent_map
 
1725
        self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
 
1726
 
 
1727
    def test_query_order(self):
 
1728
        # We should call get_cached_parent_map on all providers before we call
 
1729
        # get_parent_map. Further, we should track what entries we have found,
 
1730
        # and not re-try them.
 
1731
        pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
 
1732
        pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
 
1733
        pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
 
1734
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
 
1735
        self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
 
1736
                         stacked.get_parent_map(['a', 'b', 'c', 'd']))
 
1737
        self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
 
1738
                          # No call to pp2, because it doesn't have cached
 
1739
                          ('pp3', 'cached', ['b', 'c', 'd']),
 
1740
                          ('pp1', ['c', 'd']),
 
1741
                          ('pp2', ['c', 'd']),
 
1742
                          ('pp3', ['d']),
 
1743
                         ], self.calls)