← 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: John Arbash Meinel
  • Date: 2008-07-09 21:42:24 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080709214224-r75k87r6a01pfc3h
Restore a real weave merge to 'bzr merge --weave'.

To do so efficiently, we only add the simple LCAs to the final weave
object, unless we run into complexities with the merge graph.
This gives the same effective result as adding all the texts,
with the advantage of not having to extract all of them.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
 
1
# Copyright (C) 2007 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
from bzrlib import (
18
18
    errors,
19
19
    graph as _mod_graph,
 
20
    symbol_versioning,
20
21
    tests,
21
22
    )
22
23
from bzrlib.revision import NULL_REVISION
236
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
237
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
238
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
239
 
                    't':['i', 's'], 'u':['s', 'j'],
 
240
                    't':['i', 's'], 'u':['s', 'j'], 
240
241
                    }
241
242
 
242
243
# Graph where different walkers will race to find the common and uncommon
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
 
554
525
        graph = self.make_graph(history_shortcut)
555
526
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
556
527
 
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
 
 
570
528
    def test_recursive_unique_lca(self):
571
529
        """Test finding a unique least common ancestor.
572
530
 
703
661
        self.assertEqual((set(['e']), set(['f', 'g'])),
704
662
                         graph.find_difference('e', 'f'))
705
663
 
 
664
    def test_stacked_parents_provider(self):
 
665
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
666
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
667
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
668
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
669
                         stacked.get_parent_map(['rev1', 'rev2']))
 
670
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
671
                         stacked.get_parent_map(['rev2', 'rev1']))
 
672
        self.assertEqual({'rev2':['rev3']},
 
673
                         stacked.get_parent_map(['rev2', 'rev2']))
 
674
        self.assertEqual({'rev1':['rev4']},
 
675
                         stacked.get_parent_map(['rev1', 'rev1']))
 
676
 
706
677
    def test_iter_topo_order(self):
707
678
        graph = self.make_graph(ancestry_1)
708
679
        args = ['rev2a', 'rev3', 'rev1']
727
698
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
699
        self.assertTrue('null:' not in instrumented_provider.calls)
729
700
 
730
 
    def test_is_between(self):
731
 
        graph = self.make_graph(ancestry_1)
732
 
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
733
 
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
734
 
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
735
 
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
736
 
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
737
 
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
738
 
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
739
 
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
740
 
 
741
701
    def test_is_ancestor_boundary(self):
742
702
        """Ensure that we avoid searching the whole graph.
743
 
 
 
703
        
744
704
        This requires searching through b as a common ancestor, so we
745
705
        can identify that e is common.
746
706
        """
766
726
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
767
727
        expected['g'] = None
768
728
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
769
 
        expected.pop('a')
 
729
        expected.pop('a') 
770
730
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
771
731
 
772
732
    def test_filter_candidate_lca(self):
874
834
 
875
835
    def _run_heads_break_deeper(self, graph_dict, search):
876
836
        """Run heads on a graph-as-a-dict.
877
 
 
 
837
        
878
838
        If the search asks for the parents of 'deeper' the test will fail.
879
839
        """
880
840
        class stub(object):
1021
981
        :param next: A callable to advance the search.
1022
982
        """
1023
983
        for seen, recipe, included_keys, starts, stops in instructions:
1024
 
            # Adjust for recipe contract changes that don't vary for all the
1025
 
            # current tests.
1026
 
            recipe = ('search',) + recipe
1027
984
            next()
1028
985
            if starts is not None:
1029
986
                search.start_searching(starts)
1030
987
            if stops is not None:
1031
988
                search.stop_searching_any(stops)
1032
 
            state = search.get_state()
1033
 
            self.assertEqual(set(included_keys), state[2])
 
989
            result = search.get_result()
 
990
            self.assertEqual(recipe, result.get_recipe())
 
991
            self.assertEqual(set(included_keys), result.get_keys())
1034
992
            self.assertEqual(seen, search.seen)
1035
993
 
1036
994
    def test_breadth_first_get_result_excludes_current_pending(self):
1041
999
            })
1042
1000
        search = graph._make_breadth_first_searcher(['head'])
1043
1001
        # 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)
 
1002
        result = search.get_result()
 
1003
        self.assertEqual((set(['head']), set(['head']), 0),
 
1004
            result.get_recipe())
 
1005
        self.assertEqual(set(), result.get_keys())
1047
1006
        self.assertEqual(set(), search.seen)
1048
1007
        # using next:
1049
1008
        expected = [
1072
1031
        # Starting with nothing and adding a search works:
1073
1032
        search.start_searching(['head'])
1074
1033
        # head has been seen:
1075
 
        state = search.get_state()
1076
 
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
1077
 
            state)
 
1034
        result = search.get_result()
 
1035
        self.assertEqual((set(['head']), set(['child']), 1),
 
1036
            result.get_recipe())
 
1037
        self.assertEqual(set(['head']), result.get_keys())
1078
1038
        self.assertEqual(set(['head']), search.seen)
1079
1039
        # using next:
1080
1040
        expected = [
1109
1069
        search = graph._make_breadth_first_searcher(['head'])
1110
1070
        expected = [
1111
1071
            # NULL_REVISION and ghost1 have not been returned
1112
 
            (set(['head']),
1113
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1072
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1114
1073
             ['head'], None, [NULL_REVISION, 'ghost1']),
1115
1074
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1116
1075
            # next iteration.
1123
1082
        search = graph._make_breadth_first_searcher(['head'])
1124
1083
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1125
1084
 
1126
 
    def test_breadth_first_stop_searching_late(self):
1127
 
        # A client should be able to say 'stop node X' and have it excluded
1128
 
        # from the result even if X was seen in an older iteration of the
1129
 
        # search.
1130
 
        graph = self.make_graph({
1131
 
            'head':['middle'],
1132
 
            'middle':['child'],
1133
 
            'child':[NULL_REVISION],
1134
 
            NULL_REVISION:[],
1135
 
            })
1136
 
        search = graph._make_breadth_first_searcher(['head'])
1137
 
        expected = [
1138
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1139
 
             ['head'], None, None),
1140
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1141
 
             ['head', 'middle'], None, None),
1142
 
            # 'middle' came from the previous iteration, but we don't stop
1143
 
            # searching it until *after* advancing the searcher.
1144
 
            (set(['head', 'middle', 'child']),
1145
 
             (set(['head']), set(['middle', 'child']), 1),
1146
 
             ['head'], None, ['middle', 'child']),
1147
 
            ]
1148
 
        self.assertSeenAndResult(expected, search, search.next)
1149
 
        # using next_with_ghosts:
1150
 
        search = graph._make_breadth_first_searcher(['head'])
1151
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1152
 
 
1153
1085
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
1086
        graph = self.make_graph({
1155
1087
            'head':['child', 'ghost'],
1231
1163
        self.assertSeenAndResult(expected, search, search.next)
1232
1164
        self.assertRaises(StopIteration, search.next)
1233
1165
        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)
 
1166
        result = search.get_result()
 
1167
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1168
            result.get_recipe())
 
1169
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1239
1170
        # using next_with_ghosts:
1240
1171
        search = graph._make_breadth_first_searcher(['head'])
1241
1172
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1173
        self.assertRaises(StopIteration, search.next)
1243
1174
        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)
 
1175
        result = search.get_result()
 
1176
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1177
            result.get_recipe())
 
1178
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1249
1179
 
1250
1180
 
1251
1181
class TestFindUniqueAncestors(TestGraphBase):
1382
1312
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1383
1313
 
1384
1314
 
1385
 
class TestFindMergeOrder(TestGraphBase):
1386
 
 
1387
 
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
1388
 
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1389
 
 
1390
 
    def test_parents(self):
1391
 
        graph = self.make_graph(ancestry_1)
1392
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1393
 
                                                        ['rev3', 'rev2b'])
1394
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1395
 
                                                        ['rev2b', 'rev3'])
1396
 
 
1397
 
    def test_ancestors(self):
1398
 
        graph = self.make_graph(ancestry_1)
1399
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1400
 
                                                        ['rev1', 'rev2b'])
1401
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1402
 
                                                        ['rev2b', 'rev1'])
1403
 
 
1404
 
    def test_shortcut_one_ancestor(self):
1405
 
        # When we have enough info, we can stop searching
1406
 
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1407
 
        # Single ancestors shortcut right away
1408
 
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1409
 
 
1410
 
    def test_shortcut_after_one_ancestor(self):
1411
 
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1412
 
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
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
 
 
1470
1315
class TestCachingParentsProvider(tests.TestCase):
1471
 
    """These tests run with:
1472
 
 
1473
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1474
 
    ghost.
1475
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1476
 
    """
1477
1316
 
1478
1317
    def setUp(self):
1479
1318
        super(TestCachingParentsProvider, self).setUp()
1480
 
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
 
1319
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1481
1320
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
1321
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1483
1322
 
1498
1337
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1499
1338
        # No new calls
1500
1339
        self.assertEqual(['b'], self.inst_pp.calls)
 
1340
        self.assertEqual({'b':None}, self.caching_pp._cache)
1501
1341
 
1502
1342
    def test_get_parent_map_mixed(self):
1503
1343
        """Anything that can be returned from cache, should be"""
1514
1354
        # Use sorted because we don't care about the order, just that each is
1515
1355
        # only present 1 time.
1516
1356
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1517
 
 
1518
 
    def test_note_missing_key(self):
1519
 
        """After noting that a key is missing it is cached."""
1520
 
        self.caching_pp.note_missing_key('b')
1521
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1522
 
        self.assertEqual([], self.inst_pp.calls)
1523
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
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
 
 
1533
 
 
1534
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1535
 
    """Test the behaviour when parents are provided that were not requested."""
1536
 
 
1537
 
    def setUp(self):
1538
 
        super(TestCachingParentsProviderExtras, self).setUp()
1539
 
        class ExtraParentsProvider(object):
1540
 
 
1541
 
            def get_parent_map(self, keys):
1542
 
                return {'rev1': [], 'rev2': ['rev1',]}
1543
 
 
1544
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1545
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1546
 
            get_parent_map=self.inst_pp.get_parent_map)
1547
 
 
1548
 
    def test_uncached(self):
1549
 
        self.caching_pp.disable_cache()
1550
 
        self.assertEqual({'rev1': []},
1551
 
                         self.caching_pp.get_parent_map(['rev1']))
1552
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1553
 
        self.assertIs(None, self.caching_pp._cache)
1554
 
 
1555
 
    def test_cache_initially_empty(self):
1556
 
        self.assertEqual({}, self.caching_pp._cache)
1557
 
 
1558
 
    def test_cached(self):
1559
 
        self.assertEqual({'rev1': []},
1560
 
                         self.caching_pp.get_parent_map(['rev1']))
1561
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1562
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1563
 
                         self.caching_pp._cache)
1564
 
        self.assertEqual({'rev1': []},
1565
 
                          self.caching_pp.get_parent_map(['rev1']))
1566
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1567
 
 
1568
 
    def test_disable_cache_clears_cache(self):
1569
 
        # Put something in the cache
1570
 
        self.caching_pp.get_parent_map(['rev1'])
1571
 
        self.assertEqual(2, len(self.caching_pp._cache))
1572
 
        self.caching_pp.disable_cache()
1573
 
        self.assertIs(None, self.caching_pp._cache)
1574
 
 
1575
 
    def test_enable_cache_raises(self):
1576
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1577
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1578
 
 
1579
 
    def test_cache_misses(self):
1580
 
        self.caching_pp.get_parent_map(['rev3'])
1581
 
        self.caching_pp.get_parent_map(['rev3'])
1582
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1583
 
 
1584
 
    def test_no_cache_misses(self):
1585
 
        self.caching_pp.disable_cache()
1586
 
        self.caching_pp.enable_cache(cache_misses=False)
1587
 
        self.caching_pp.get_parent_map(['rev3'])
1588
 
        self.caching_pp.get_parent_map(['rev3'])
1589
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1590
 
 
1591
 
    def test_cache_extras(self):
1592
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1593
 
        self.assertEqual({'rev2': ['rev1']},
1594
 
                         self.caching_pp.get_parent_map(['rev2']))
1595
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
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
 
 
1605
 
 
1606
 
class TestCollapseLinearRegions(tests.TestCase):
1607
 
 
1608
 
    def assertCollapsed(self, collapsed, original):
1609
 
        self.assertEqual(collapsed,
1610
 
                         _mod_graph.collapse_linear_regions(original))
1611
 
 
1612
 
    def test_collapse_nothing(self):
1613
 
        d = {1:[2, 3], 2:[], 3:[]}
1614
 
        self.assertCollapsed(d, d)
1615
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1616
 
        self.assertCollapsed(d, d)
1617
 
 
1618
 
    def test_collapse_chain(self):
1619
 
        # Any time we have a linear chain, we should be able to collapse
1620
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1621
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1622
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1623
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1624
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1625
 
        self.assertCollapsed({5:[2], 2:[]}, d)
1626
 
 
1627
 
    def test_collapse_with_multiple_children(self):
1628
 
        #    7
1629
 
        #    |
1630
 
        #    6
1631
 
        #   / \
1632
 
        #  4   5
1633
 
        #  |   |
1634
 
        #  2   3
1635
 
        #   \ /
1636
 
        #    1
1637
 
        #
1638
 
        # 4 and 5 cannot be removed because 6 has 2 children
1639
 
        # 2 and 3 cannot be removed because 1 has 2 parents
1640
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1641
 
        self.assertCollapsed(d, d)
1642
 
 
1643
 
 
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)