← 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: Jelmer Vernooij
  • Date: 2012-01-27 19:05:43 UTC
  • mto: This revision was merged to the branch mainline in revision 6450.
  • Revision ID: jelmer@samba.org-20120127190543-vk350mv4a0c7aug2
Fix weave test.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007 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
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
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
237
236
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
237
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
238
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
 
                    't':['i', 's'], 'u':['s', 'j'], 
 
239
                    't':['i', 's'], 'u':['s', 'j'],
241
240
                    }
242
241
 
243
242
# Graph where different walkers will race to find the common and uncommon
283
282
#     |/
284
283
#     j
285
284
#
286
 
# y is found to be common right away, but is the start of a long series of
 
285
# x is found to be common right away, but is the start of a long series of
287
286
# common commits.
288
287
# o is actually common, but the i-j shortcut makes it look like it is actually
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.
 
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.
291
290
# k-n exists so that the second pass still has nodes that are worth searching,
292
291
# rather than instantly cancelling the extra walker.
293
292
 
396
395
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
397
396
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
398
397
 
 
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']}
399
420
 
400
421
 
401
422
class InstrumentedParentsProvider(object):
403
424
    def __init__(self, parents_provider):
404
425
        self.calls = []
405
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
406
432
 
407
433
    def get_parent_map(self, nodes):
408
434
        self.calls.extend(nodes)
409
435
        return self._real_parents_provider.get_parent_map(nodes)
410
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
 
 
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
 
411
480
 
412
481
class TestGraph(TestCaseWithMemoryTransport):
413
482
 
485
554
        graph = self.make_graph(history_shortcut)
486
555
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
487
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
 
488
570
    def test_recursive_unique_lca(self):
489
571
        """Test finding a unique least common ancestor.
490
572
 
621
703
        self.assertEqual((set(['e']), set(['f', 'g'])),
622
704
                         graph.find_difference('e', 'f'))
623
705
 
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
 
 
637
706
    def test_iter_topo_order(self):
638
707
        graph = self.make_graph(ancestry_1)
639
708
        args = ['rev2a', 'rev3', 'rev1']
658
727
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
659
728
        self.assertTrue('null:' not in instrumented_provider.calls)
660
729
 
 
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
 
661
741
    def test_is_ancestor_boundary(self):
662
742
        """Ensure that we avoid searching the whole graph.
663
 
        
 
743
 
664
744
        This requires searching through b as a common ancestor, so we
665
745
        can identify that e is common.
666
746
        """
686
766
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
687
767
        expected['g'] = None
688
768
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
689
 
        expected.pop('a') 
 
769
        expected.pop('a')
690
770
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
691
771
 
692
772
    def test_filter_candidate_lca(self):
794
874
 
795
875
    def _run_heads_break_deeper(self, graph_dict, search):
796
876
        """Run heads on a graph-as-a-dict.
797
 
        
 
877
 
798
878
        If the search asks for the parents of 'deeper' the test will fail.
799
879
        """
800
880
        class stub(object):
941
1021
        :param next: A callable to advance the search.
942
1022
        """
943
1023
        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
944
1027
            next()
945
1028
            if starts is not None:
946
1029
                search.start_searching(starts)
947
1030
            if stops is not None:
948
1031
                search.stop_searching_any(stops)
949
 
            result = search.get_result()
950
 
            self.assertEqual(recipe, result.get_recipe())
951
 
            self.assertEqual(set(included_keys), result.get_keys())
 
1032
            state = search.get_state()
 
1033
            self.assertEqual(set(included_keys), state[2])
952
1034
            self.assertEqual(seen, search.seen)
953
1035
 
954
1036
    def test_breadth_first_get_result_excludes_current_pending(self):
959
1041
            })
960
1042
        search = graph._make_breadth_first_searcher(['head'])
961
1043
        # At the start, nothing has been seen, to its all excluded:
962
 
        result = search.get_result()
963
 
        self.assertEqual((set(['head']), set(['head']), 0),
964
 
            result.get_recipe())
965
 
        self.assertEqual(set(), result.get_keys())
 
1044
        state = search.get_state()
 
1045
        self.assertEqual((set(['head']), set(['head']), set()),
 
1046
            state)
966
1047
        self.assertEqual(set(), search.seen)
967
1048
        # using next:
968
1049
        expected = [
991
1072
        # Starting with nothing and adding a search works:
992
1073
        search.start_searching(['head'])
993
1074
        # head has been seen:
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())
 
1075
        state = search.get_state()
 
1076
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
 
1077
            state)
998
1078
        self.assertEqual(set(['head']), search.seen)
999
1079
        # using next:
1000
1080
        expected = [
1029
1109
        search = graph._make_breadth_first_searcher(['head'])
1030
1110
        expected = [
1031
1111
            # NULL_REVISION and ghost1 have not been returned
1032
 
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
 
1112
            (set(['head']),
 
1113
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1033
1114
             ['head'], None, [NULL_REVISION, 'ghost1']),
1034
1115
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1035
1116
            # next iteration.
1042
1123
        search = graph._make_breadth_first_searcher(['head'])
1043
1124
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1044
1125
 
 
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
 
1045
1153
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1046
1154
        graph = self.make_graph({
1047
1155
            'head':['child', 'ghost'],
1123
1231
        self.assertSeenAndResult(expected, search, search.next)
1124
1232
        self.assertRaises(StopIteration, search.next)
1125
1233
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
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())
 
1234
        state = search.get_state()
 
1235
        self.assertEqual(
 
1236
            (set(['ghost', 'head']), set(['ghost']),
 
1237
                set(['head', NULL_REVISION])),
 
1238
            state)
1130
1239
        # using next_with_ghosts:
1131
1240
        search = graph._make_breadth_first_searcher(['head'])
1132
1241
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1133
1242
        self.assertRaises(StopIteration, search.next)
1134
1243
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
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
 
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):
1157
1252
 
1158
1253
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1159
1254
        actual = graph.find_unique_ancestors(node, common)
1228
1323
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1229
1324
 
1230
1325
 
 
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
 
1231
1470
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
    """
1232
1477
 
1233
1478
    def setUp(self):
1234
1479
        super(TestCachingParentsProvider, self).setUp()
1235
 
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
 
1480
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1236
1481
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1237
1482
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1238
1483
 
1253
1498
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1254
1499
        # No new calls
1255
1500
        self.assertEqual(['b'], self.inst_pp.calls)
1256
 
        self.assertEqual({'b':None}, self.caching_pp._cache)
1257
1501
 
1258
1502
    def test_get_parent_map_mixed(self):
1259
1503
        """Anything that can be returned from cache, should be"""
1270
1514
        # Use sorted because we don't care about the order, just that each is
1271
1515
        # only present 1 time.
1272
1516
        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)