/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Robert Collins
  • Date: 2009-03-13 02:25:46 UTC
  • mfrom: (4133 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4183.
  • Revision ID: robertc@robertcollins.net-20090313022546-e7de5zsdkbay5okf
Merge .dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
237
237
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
238
238
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
239
239
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
240
 
                    't':['i', 's'], 'u':['s', 'j'], 
 
240
                    't':['i', 's'], 'u':['s', 'j'],
241
241
                    }
242
242
 
243
243
# Graph where different walkers will race to find the common and uncommon
698
698
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
699
699
        self.assertTrue('null:' not in instrumented_provider.calls)
700
700
 
 
701
    def test_is_between(self):
 
702
        graph = self.make_graph(ancestry_1)
 
703
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
 
704
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
 
705
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
 
706
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
 
707
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
 
708
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
 
709
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
 
710
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
 
711
 
701
712
    def test_is_ancestor_boundary(self):
702
713
        """Ensure that we avoid searching the whole graph.
703
 
        
 
714
 
704
715
        This requires searching through b as a common ancestor, so we
705
716
        can identify that e is common.
706
717
        """
726
737
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
727
738
        expected['g'] = None
728
739
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
729
 
        expected.pop('a') 
 
740
        expected.pop('a')
730
741
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
731
742
 
732
743
    def test_filter_candidate_lca(self):
834
845
 
835
846
    def _run_heads_break_deeper(self, graph_dict, search):
836
847
        """Run heads on a graph-as-a-dict.
837
 
        
 
848
 
838
849
        If the search asks for the parents of 'deeper' the test will fail.
839
850
        """
840
851
        class stub(object):
1069
1080
        search = graph._make_breadth_first_searcher(['head'])
1070
1081
        expected = [
1071
1082
            # NULL_REVISION and ghost1 have not been returned
1072
 
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
 
1083
            (set(['head']),
 
1084
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
1073
1085
             ['head'], None, [NULL_REVISION, 'ghost1']),
1074
1086
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1075
1087
            # next iteration.
1082
1094
        search = graph._make_breadth_first_searcher(['head'])
1083
1095
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1084
1096
 
 
1097
    def test_breadth_first_stop_searching_late(self):
 
1098
        # A client should be able to say 'stop node X' and have it excluded
 
1099
        # from the result even if X was seen in an older iteration of the
 
1100
        # search.
 
1101
        graph = self.make_graph({
 
1102
            'head':['middle'],
 
1103
            'middle':['child'],
 
1104
            'child':[NULL_REVISION],
 
1105
            NULL_REVISION:[],
 
1106
            })
 
1107
        search = graph._make_breadth_first_searcher(['head'])
 
1108
        expected = [
 
1109
            (set(['head']), (set(['head']), set(['middle']), 1),
 
1110
             ['head'], None, None),
 
1111
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
 
1112
             ['head', 'middle'], None, None),
 
1113
            # 'middle' came from the previous iteration, but we don't stop
 
1114
            # searching it until *after* advancing the searcher.
 
1115
            (set(['head', 'middle', 'child']),
 
1116
             (set(['head']), set(['middle', 'child']), 1),
 
1117
             ['head'], None, ['middle', 'child']),
 
1118
            ]
 
1119
        self.assertSeenAndResult(expected, search, search.next)
 
1120
        # using next_with_ghosts:
 
1121
        search = graph._make_breadth_first_searcher(['head'])
 
1122
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
1123
 
1085
1124
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1086
1125
        graph = self.make_graph({
1087
1126
            'head':['child', 'ghost'],
1386
1425
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1387
1426
 
1388
1427
 
 
1428
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
 
1429
    """Test the behaviour when parents are provided that were not requested."""
 
1430
 
 
1431
    def setUp(self):
 
1432
        super(TestCachingParentsProviderExtras, self).setUp()
 
1433
        class ExtraParentsProvider(object):
 
1434
 
 
1435
            def get_parent_map(self, keys):
 
1436
                return {'rev1': [], 'rev2': ['rev1',]}
 
1437
 
 
1438
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
 
1439
        self.caching_pp = _mod_graph.CachingParentsProvider(
 
1440
            get_parent_map=self.inst_pp.get_parent_map)
 
1441
 
 
1442
    def test_uncached(self):
 
1443
        self.caching_pp.disable_cache()
 
1444
        self.assertEqual({'rev1': []},
 
1445
                         self.caching_pp.get_parent_map(['rev1']))
 
1446
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1447
        self.assertIs(None, self.caching_pp._cache)
 
1448
 
 
1449
    def test_cache_initially_empty(self):
 
1450
        self.assertEqual({}, self.caching_pp._cache)
 
1451
 
 
1452
    def test_cached(self):
 
1453
        self.assertEqual({'rev1': []},
 
1454
                         self.caching_pp.get_parent_map(['rev1']))
 
1455
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1456
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
 
1457
                         self.caching_pp._cache)
 
1458
        self.assertEqual({'rev1': []},
 
1459
                          self.caching_pp.get_parent_map(['rev1']))
 
1460
        self.assertEqual(['rev1'], self.inst_pp.calls)
 
1461
 
 
1462
    def test_disable_cache_clears_cache(self):
 
1463
        # Put something in the cache
 
1464
        self.caching_pp.get_parent_map(['rev1'])
 
1465
        self.assertEqual(2, len(self.caching_pp._cache))
 
1466
        self.caching_pp.disable_cache()
 
1467
        self.assertIs(None, self.caching_pp._cache)
 
1468
 
 
1469
    def test_enable_cache_raises(self):
 
1470
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
 
1471
        self.assertEqual('Cache enabled when already enabled.', str(e))
 
1472
 
 
1473
    def test_cache_misses(self):
 
1474
        self.caching_pp.get_parent_map(['rev3'])
 
1475
        self.caching_pp.get_parent_map(['rev3'])
 
1476
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1477
 
 
1478
    def test_no_cache_misses(self):
 
1479
        self.caching_pp.disable_cache()
 
1480
        self.caching_pp.enable_cache(cache_misses=False)
 
1481
        self.caching_pp.get_parent_map(['rev3'])
 
1482
        self.caching_pp.get_parent_map(['rev3'])
 
1483
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
 
1484
 
 
1485
    def test_cache_extras(self):
 
1486
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
 
1487
        self.assertEqual({'rev2': ['rev1']},
 
1488
                         self.caching_pp.get_parent_map(['rev2']))
 
1489
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1490
 
 
1491
 
1389
1492
class TestCollapseLinearRegions(tests.TestCase):
1390
1493
 
1391
1494
    def assertCollapsed(self, collapsed, original):
1422
1525
        # 2 and 3 cannot be removed because 1 has 2 parents
1423
1526
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1424
1527
        self.assertCollapsed(d, d)
 
1528
 
 
1529
 
 
1530
class TestPendingAncestryResult(TestCaseWithMemoryTransport):
 
1531
    """Tests for bzrlib.graph.PendingAncestryResult."""
 
1532
 
 
1533
    def test_get_keys(self):
 
1534
        builder = self.make_branch_builder('b')
 
1535
        builder.start_series()
 
1536
        builder.build_snapshot('rev-1', None, [
 
1537
            ('add', ('', 'root-id', 'directory', ''))])
 
1538
        builder.build_snapshot('rev-2', ['rev-1'], [])
 
1539
        builder.finish_series()
 
1540
        repo = builder.get_branch().repository
 
1541
        repo.lock_read()
 
1542
        self.addCleanup(repo.unlock)
 
1543
        par = _mod_graph.PendingAncestryResult(['rev-2'], repo)
 
1544
        self.assertEqual(set(['rev-1', 'rev-2']), set(par.get_keys()))
 
1545
 
 
1546
    def test_get_keys_excludes_null(self):
 
1547
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
 
1548
        # somewhere other than the last element, which can happen in real
 
1549
        # ancestries.
 
1550
        class StubGraph(object):
 
1551
            def iter_ancestry(self, keys):
 
1552
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
 
1553
        par = _mod_graph.PendingAncestryResult(['rev-3'], None)
 
1554
        par_keys = par._get_keys(StubGraph())
 
1555
        # Only the non-null keys from the ancestry appear.
 
1556
        self.assertEqual(set(['foo']), set(par_keys))
 
1557