← 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: Canonical.com Patch Queue Manager
  • Date: 2008-05-06 11:40:10 UTC
  • mfrom: (3400.1.3 trivial)
  • Revision ID: pqm@pqm.ubuntu.com-20080506114010-jwclr2qtiekvawjg
Remove erroneous creation of branch-name file in cmd_branch

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
282
283
#     |/
283
284
#     j
284
285
#
285
 
# x is found to be common right away, but is the start of a long series of
 
286
# y is found to be common right away, but is the start of a long series of
286
287
# common commits.
287
288
# o is actually common, but the i-j shortcut makes it look like it is actually
288
 
# unique to j at first, you have to traverse all of x->o to find it.
289
 
# q,m gives the walker from j a common point to stop searching, as does p,f.
 
289
# unique to j at first, you have to traverse all of y->o to find it.
 
290
# q,n give the walker from j a common point to stop searching, as does p,f.
290
291
# k-n exists so that the second pass still has nodes that are worth searching,
291
292
# rather than instantly cancelling the extra walker.
292
293
 
395
396
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
396
397
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
397
398
 
398
 
# A graph that shows we can shortcut finding revnos when reaching them from the
399
 
# side.
400
 
#  NULL_REVISION
401
 
#       |
402
 
#       a
403
 
#       |
404
 
#       b
405
 
#       |
406
 
#       c
407
 
#       |
408
 
#       d
409
 
#       |
410
 
#       e
411
 
#      / \
412
 
#     f   g
413
 
#     |
414
 
#     h
415
 
#     |
416
 
#     i
417
 
 
418
 
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
419
 
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
420
399
 
421
400
 
422
401
class InstrumentedParentsProvider(object):
424
403
    def __init__(self, parents_provider):
425
404
        self.calls = []
426
405
        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
406
 
433
407
    def get_parent_map(self, nodes):
434
408
        self.calls.extend(nodes)
435
409
        return self._real_parents_provider.get_parent_map(nodes)
436
410
 
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
 
 
463
 
class TestGraphBase(tests.TestCase):
464
 
 
465
 
    def make_graph(self, ancestors):
466
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
467
 
 
468
 
    def make_breaking_graph(self, ancestors, break_on):
469
 
        """Make a Graph that raises an exception if we hit a node."""
470
 
        g = self.make_graph(ancestors)
471
 
        orig_parent_map = g.get_parent_map
472
 
        def get_parent_map(keys):
473
 
            bad_keys = set(keys).intersection(break_on)
474
 
            if bad_keys:
475
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
476
 
            return orig_parent_map(keys)
477
 
        g.get_parent_map = get_parent_map
478
 
        return g
479
 
 
480
411
 
481
412
class TestGraph(TestCaseWithMemoryTransport):
482
413
 
554
485
        graph = self.make_graph(history_shortcut)
555
486
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
556
487
 
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
488
    def test_recursive_unique_lca(self):
571
489
        """Test finding a unique least common ancestor.
572
490
 
703
621
        self.assertEqual((set(['e']), set(['f', 'g'])),
704
622
                         graph.find_difference('e', 'f'))
705
623
 
 
624
    def test_stacked_parents_provider(self):
 
625
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
626
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
627
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
628
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
629
                         stacked.get_parent_map(['rev1', 'rev2']))
 
630
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
631
                         stacked.get_parent_map(['rev2', 'rev1']))
 
632
        self.assertEqual({'rev2':['rev3']},
 
633
                         stacked.get_parent_map(['rev2', 'rev2']))
 
634
        self.assertEqual({'rev1':['rev4']},
 
635
                         stacked.get_parent_map(['rev1', 'rev1']))
 
636
 
706
637
    def test_iter_topo_order(self):
707
638
        graph = self.make_graph(ancestry_1)
708
639
        args = ['rev2a', 'rev3', 'rev1']
727
658
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
659
        self.assertTrue('null:' not in instrumented_provider.calls)
729
660
 
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
661
    def test_is_ancestor_boundary(self):
742
662
        """Ensure that we avoid searching the whole graph.
743
 
 
 
663
        
744
664
        This requires searching through b as a common ancestor, so we
745
665
        can identify that e is common.
746
666
        """
766
686
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
767
687
        expected['g'] = None
768
688
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
769
 
        expected.pop('a')
 
689
        expected.pop('a') 
770
690
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
771
691
 
772
692
    def test_filter_candidate_lca(self):
874
794
 
875
795
    def _run_heads_break_deeper(self, graph_dict, search):
876
796
        """Run heads on a graph-as-a-dict.
877
 
 
 
797
        
878
798
        If the search asks for the parents of 'deeper' the test will fail.
879
799
        """
880
800
        class stub(object):
1021
941
        :param next: A callable to advance the search.
1022
942
        """
1023
943
        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
944
            next()
1028
945
            if starts is not None:
1029
946
                search.start_searching(starts)
1030
947
            if stops is not None:
1031
948
                search.stop_searching_any(stops)
1032
 
            state = search.get_state()
1033
 
            self.assertEqual(set(included_keys), state[2])
 
949
            result = search.get_result()
 
950
            self.assertEqual(recipe, result.get_recipe())
 
951
            self.assertEqual(set(included_keys), result.get_keys())
1034
952
            self.assertEqual(seen, search.seen)
1035
953
 
1036
954
    def test_breadth_first_get_result_excludes_current_pending(self):
1041
959
            })
1042
960
        search = graph._make_breadth_first_searcher(['head'])
1043
961
        # 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)
 
962
        result = search.get_result()
 
963
        self.assertEqual((set(['head']), set(['head']), 0),
 
964
            result.get_recipe())
 
965
        self.assertEqual(set(), result.get_keys())
1047
966
        self.assertEqual(set(), search.seen)
1048
967
        # using next:
1049
968
        expected = [
1072
991
        # Starting with nothing and adding a search works:
1073
992
        search.start_searching(['head'])
1074
993
        # head has been seen:
1075
 
        state = search.get_state()
1076
 
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
1077
 
            state)
 
994
        result = search.get_result()
 
995
        self.assertEqual((set(['head']), set(['child']), 1),
 
996
            result.get_recipe())
 
997
        self.assertEqual(set(['head']), result.get_keys())
1078
998
        self.assertEqual(set(['head']), search.seen)
1079
999
        # using next:
1080
1000
        expected = [
1109
1029
        search = graph._make_breadth_first_searcher(['head'])
1110
1030
        expected = [
1111
1031
            # NULL_REVISION and ghost1 have not been returned
1112
 
            (set(['head']),
1113
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1032
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1114
1033
             ['head'], None, [NULL_REVISION, 'ghost1']),
1115
1034
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1116
1035
            # next iteration.
1123
1042
        search = graph._make_breadth_first_searcher(['head'])
1124
1043
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1125
1044
 
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
1045
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
1046
        graph = self.make_graph({
1155
1047
            'head':['child', 'ghost'],
1231
1123
        self.assertSeenAndResult(expected, search, search.next)
1232
1124
        self.assertRaises(StopIteration, search.next)
1233
1125
        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)
 
1126
        result = search.get_result()
 
1127
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1128
            result.get_recipe())
 
1129
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1239
1130
        # using next_with_ghosts:
1240
1131
        search = graph._make_breadth_first_searcher(['head'])
1241
1132
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1133
        self.assertRaises(StopIteration, search.next)
1243
1134
        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)
1249
 
 
1250
 
 
1251
 
class TestFindUniqueAncestors(TestGraphBase):
 
1135
        result = search.get_result()
 
1136
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
1137
            result.get_recipe())
 
1138
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
1139
 
 
1140
 
 
1141
class TestFindUniqueAncestors(tests.TestCase):
 
1142
 
 
1143
    def make_graph(self, ancestors):
 
1144
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
1145
 
 
1146
    def make_breaking_graph(self, ancestors, break_on):
 
1147
        """Make a Graph that raises an exception if we hit a node."""
 
1148
        g = self.make_graph(ancestors)
 
1149
        orig_parent_map = g.get_parent_map
 
1150
        def get_parent_map(keys):
 
1151
            bad_keys = set(keys).intersection(break_on)
 
1152
            if bad_keys:
 
1153
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
 
1154
            return orig_parent_map(keys)
 
1155
        g.get_parent_map = get_parent_map
 
1156
        return g
1252
1157
 
1253
1158
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1254
1159
        actual = graph.find_unique_ancestors(node, common)
1323
1228
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1324
1229
 
1325
1230
 
1326
 
class TestGraphFindDistanceToNull(TestGraphBase):
1327
 
    """Test an api that should be able to compute a revno"""
1328
 
 
1329
 
    def assertFindDistance(self, revno, graph, target_id, known_ids):
1330
 
        """Assert the output of Graph.find_distance_to_null()"""
1331
 
        actual = graph.find_distance_to_null(target_id, known_ids)
1332
 
        self.assertEqual(revno, actual)
1333
 
 
1334
 
    def test_nothing_known(self):
1335
 
        graph = self.make_graph(ancestry_1)
1336
 
        self.assertFindDistance(0, graph, NULL_REVISION, [])
1337
 
        self.assertFindDistance(1, graph, 'rev1', [])
1338
 
        self.assertFindDistance(2, graph, 'rev2a', [])
1339
 
        self.assertFindDistance(2, graph, 'rev2b', [])
1340
 
        self.assertFindDistance(3, graph, 'rev3', [])
1341
 
        self.assertFindDistance(4, graph, 'rev4', [])
1342
 
 
1343
 
    def test_rev_is_ghost(self):
1344
 
        graph = self.make_graph(ancestry_1)
1345
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1346
 
                              graph.find_distance_to_null, 'rev_missing', [])
1347
 
        self.assertEqual('rev_missing', e.revision_id)
1348
 
        self.assertEqual('rev_missing', e.ghost_revision_id)
1349
 
 
1350
 
    def test_ancestor_is_ghost(self):
1351
 
        graph = self.make_graph({'rev':['parent']})
1352
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1353
 
                              graph.find_distance_to_null, 'rev', [])
1354
 
        self.assertEqual('rev', e.revision_id)
1355
 
        self.assertEqual('parent', e.ghost_revision_id)
1356
 
 
1357
 
    def test_known_in_ancestry(self):
1358
 
        graph = self.make_graph(ancestry_1)
1359
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1360
 
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1361
 
 
1362
 
    def test_known_in_ancestry_limits(self):
1363
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1364
 
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1365
 
 
1366
 
    def test_target_is_ancestor(self):
1367
 
        graph = self.make_graph(ancestry_1)
1368
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1369
 
 
1370
 
    def test_target_is_ancestor_limits(self):
1371
 
        """We shouldn't search all history if we run into ourselves"""
1372
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1373
 
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1374
 
 
1375
 
    def test_target_parallel_to_known_limits(self):
1376
 
        # Even though the known revision isn't part of the other ancestry, they
1377
 
        # eventually converge
1378
 
        graph = self.make_breaking_graph(with_tail, ['a'])
1379
 
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
1380
 
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
1381
 
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
1382
 
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1383
 
 
1384
 
 
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
1231
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
1232
 
1478
1233
    def setUp(self):
1479
1234
        super(TestCachingParentsProvider, self).setUp()
1480
 
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
 
1235
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1481
1236
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
1237
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1483
1238
 
1498
1253
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1499
1254
        # No new calls
1500
1255
        self.assertEqual(['b'], self.inst_pp.calls)
 
1256
        self.assertEqual({'b':None}, self.caching_pp._cache)
1501
1257
 
1502
1258
    def test_get_parent_map_mixed(self):
1503
1259
        """Anything that can be returned from cache, should be"""
1514
1270
        # Use sorted because we don't care about the order, just that each is
1515
1271
        # only present 1 time.
1516
1272
        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)